{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Count of Range Sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #binary-indexed-tree #segment-tree #array #binary-search #divide-and-conquer #ordered-set #merge-sort"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树状数组 #线段树 #数组 #二分查找 #分治 #有序集合 #归并排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: countRangeSum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #区间和的个数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数数组 <code>nums</code> 以及两个整数 <code>lower</code> 和 <code>upper</code> 。求数组中，值位于范围 <code>[lower, upper]</code> （包含 <code>lower</code> 和 <code>upper</code>）之内的 <strong>区间和的个数</strong> 。</p>\n",
    "\n",
    "<p><strong>区间和</strong> <code>S(i, j)</code> 表示在 <code>nums</code> 中，位置从 <code>i</code> 到 <code>j</code> 的元素之和，包含 <code>i</code> 和 <code>j</code> (<code>i</code> ≤ <code>j</code>)。</p>\n",
    "\n",
    "<p> </p>\n",
    "<strong>示例 1：</strong>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [-2,5,-1], lower = -2, upper = 2\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>存在三个区间：[0,0]、[2,2] 和 [0,2] ，对应的区间和分别是：-2 、-1 、2 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [0], lower = 0, upper = 0\n",
    "<strong>输出：</strong>1\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= nums.length <= 10<sup>5</sup></code></li>\n",
    "\t<li><code>-2<sup>31</sup> <= nums[i] <= 2<sup>31</sup> - 1</code></li>\n",
    "\t<li><code>-10<sup>5</sup> <= lower <= upper <= 10<sup>5</sup></code></li>\n",
    "\t<li>题目数据保证答案是一个 <strong>32 位</strong> 的整数</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [count-of-range-sum](https://leetcode.cn/problems/count-of-range-sum/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [count-of-range-sum](https://leetcode.cn/problems/count-of-range-sum/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[-2,5,-1]\\n-2\\n2', '[0]\\n0\\n0']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from bisect import bisect_left, bisect_right\n",
    "\n",
    "class Solution:\n",
    "  def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "    n = len(nums)\n",
    "    pre_sum = [0] * (n + 1)\n",
    "    for i in range(n):\n",
    "      pre_sum[i + 1] = pre_sum[i] + nums[i]\n",
    "    ans = 0\n",
    "    def mergeSort(arr, l, r):\n",
    "      nonlocal ans, lower, upper\n",
    "      if l > r: return []\n",
    "      if l == r: return [arr[l]]\n",
    "      mid = l + (r - l) // 2\n",
    "      arr1 = mergeSort(arr, l, mid)\n",
    "      arr2 = mergeSort(arr, mid + 1, r)\n",
    "      for x in arr1:\n",
    "        left, right = x + lower, x + upper\n",
    "        ans += bisect_right(arr2, right) - bisect_left(arr2, left)\n",
    "      arr3 = []\n",
    "      n1, n2 = len(arr1), len(arr2)\n",
    "      i = j = 0\n",
    "      while i < n1 or j < n2:\n",
    "        if i == n1:\n",
    "          arr3.append(arr2[j])\n",
    "          j += 1\n",
    "        elif j == n2 or arr1[i] <= arr2[j]:\n",
    "          arr3.append(arr1[i])\n",
    "          i += 1\n",
    "        else:\n",
    "          arr3.append(arr2[j])\n",
    "          j += 1\n",
    "      return arr3\n",
    "    mergeSort(pre_sum, 0, n)\n",
    "    return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        pre=[0]\n",
    "        temp=0\n",
    "        l=len(nums)\n",
    "        count=0\n",
    "        for i in range(l):\n",
    "            temp+=nums[i]\n",
    "            r=bisect.bisect_right(pre,temp-lower)\n",
    "            l=bisect.bisect_left(pre,temp-upper)\n",
    "            count+=r-l\n",
    "            #pre.append(temp)\n",
    "            bisect.insort(pre,temp)\n",
    "        #print(pre)\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        sums = 0\n",
    "        sl, ans = SortedList(), 0\n",
    "        sl.add(sums)\n",
    "        for v in nums:\n",
    "            sums += v\n",
    "            id1 = sl.bisect_left(sums - upper)\n",
    "            id2 = sl.bisect_right(sums - lower)\n",
    "            #print(v, sums, id1, id2)\n",
    "            ans += id2 - id1\n",
    "            sl.add(sums)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 一个思考：\n",
    "# 【思考】前缀和排序之后，原始序列中的各个数字之间的顺序就改变了，如何将排好序之后的序列与原始序列对应起来？\n",
    "# 原始数组未排序，但您使用前缀和而不是原始值对其进行排序。 数组的前缀和是从开头到当前索引的所有元素的总和。 例如，如果 nums = [1, -2, 3, 4]，则前缀和为 [0, 1, -1, 2, 6]。 您对前缀和进行排序，而不是对原始值进行排序，因为范围和 S(i, j) 等于 j 处的前缀和减去 i - 1 处的前缀和。例如，S(1, 3) = 5， 等于 6 - 1。\n",
    "# 【原始数组的顺序不会改变，但前缀和的顺序会改变。】 但是，您仍然可以获得正确的答案，因为您只关心前缀和之间的差异，而不关心它们的绝对值。 当合并两个已排序的一半时，可以使用两个指针来查找满足条件 nums[j] - num <= upper 和 nums[i] - num >= lower 的对，其中 num 是左侧的当前元素 一半。 您可以这样做，因为每一半中的元素都已经排序，因此您可以相应地移动指针。 \n",
    "# 您不需要知道原始数组中元素的确切索引，只需要知道它们在前缀和数组中的相对位置。\n",
    "# 另一个问题是，所有的结果一定满足i<j（因为已排序）\n",
    "class Solution:\n",
    "    def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        self.n = len(nums)\n",
    "        n = self.n\n",
    "        self.tmp = [0] * (n + 1)   #  tmp是排序前的左右两半，待归并的序列, nums是排好序的序列\n",
    "        self.lower = lower\n",
    "        self.upper = upper\n",
    "        self.count = 0\n",
    "        preSum = [0] * (n + 1)\n",
    "        # 【思考】前缀和排序之后，原始序列中的各个数字之间的顺序就改变了，如何将排好序之后的序列与原始序列对应起来？\n",
    "        # preSum[0] = nums[0]\n",
    "        for i in range(1, n + 1):\n",
    "            preSum[i] = preSum[i - 1] + nums[i - 1]\n",
    "        self.sort_(preSum, 0, n)\n",
    "        return self.count\n",
    "    \n",
    "    def sort_(self, nums, left, right):\n",
    "        if left >= right:\n",
    "            return \n",
    "        mid = left + (right - left) // 2\n",
    "        self.sort_(nums, left, mid)\n",
    "        self.sort_(nums, mid + 1, right)\n",
    "        self.merge(nums, left, mid, right)\n",
    "    \n",
    "    \n",
    "    def merge(self, nums, left, mid, right):\n",
    "        self.tmp[left:right + 1] = nums[left: right + 1]\n",
    "        \n",
    "        i = mid + 1\n",
    "        j = mid + 1\n",
    "        for num in nums[left: mid + 1]:\n",
    "            # while i <= right and  nums[i + 1] - num >= self.lower:\n",
    "            while i <= right and  nums[i] - num < self.lower:   #（注意小于号） i==right的时候，就是最后一个元素，所以不需要再+1（会越界）\n",
    "                i += 1\n",
    "            while j <= right and nums[j] - num <= self.upper:    # nums[j] - num是前缀和\n",
    "                j += 1\n",
    "            self.count += j - i\n",
    "            # j 的值是第一个超过上限的索引，i 的值是第一个满足或超过下限的索引。 因此，有效对的数量是 j - i，而不是 j - i - 1。\n",
    "        \n",
    "        # while i <= mid and j <= right:   #【注意如何取前缀和】\n",
    "        #     while nums[j + 1] - nums[i] >= self.lower and nums[j + 1] - nums[i] <= self.uppper:\n",
    "        #         # 每一轮固定i，移动j，确定边界处的j之后，[i...j]就是区间个数\n",
    "        #         j += 1 \n",
    "        #     self.count += \n",
    "        #     i += 1\n",
    "\n",
    "        i = left\n",
    "        j = mid + 1\n",
    "        for p in range(left, right + 1):\n",
    "            if i == mid + 1:\n",
    "                nums[p] = self.tmp[j]\n",
    "                j += 1\n",
    "            elif j == right + 1:\n",
    "                nums[p] = self.tmp[i]\n",
    "                i += 1\n",
    "            elif self.tmp[i] < self.tmp[j]:\n",
    "                nums[p] = self.tmp[i]\n",
    "                i += 1\n",
    "            elif self.tmp[i] >= self.tmp[j]:\n",
    "                nums[p] = self.tmp[j]\n",
    "                j += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.ans = 0\n",
    "    def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        self.lower = lower\n",
    "        self.upper = upper\n",
    "\n",
    "        pre_sum = [0]\n",
    "        for num in nums:\n",
    "            pre_sum.append(num + pre_sum[-1])\n",
    "\n",
    "        self.sort(pre_sum)\n",
    "\n",
    "        return self.ans\n",
    "\n",
    "    def sort(self,nums):\n",
    "        n = len(nums)\n",
    "        if n == 1:\n",
    "            return nums\n",
    "        mid = n // 2\n",
    "        l_arr = nums[:mid]\n",
    "        r_arr = nums[mid:]\n",
    "\n",
    "        l_arr = self.sort(l_arr)\n",
    "        r_arr = self.sort(r_arr)\n",
    "\n",
    "        return self.merge(l_arr , r_arr)\n",
    "    \n",
    "    def merge(self,l_arr,r_arr):\n",
    "        l = 0\n",
    "        r = 0\n",
    "        arr = []\n",
    "        start = 0\n",
    "        end = 0\n",
    "        for i in range(len(l_arr)):\n",
    "            \n",
    "            while(start < len(r_arr) and r_arr[start] - l_arr[i] < self.lower):\n",
    "                start += 1\n",
    "            \n",
    "            while(end < len(r_arr) and r_arr[end] - l_arr[i] <= self.upper):\n",
    "                end += 1\n",
    "            \n",
    "            self.ans += (end - start)\n",
    "        while(l < len(l_arr) and r < len(r_arr)):\n",
    "            if(l_arr[l] <= r_arr[r]):\n",
    "                arr.append(l_arr[l])\n",
    "                l += 1\n",
    "            else:\n",
    "                arr.append(r_arr[r])\n",
    "                r += 1\n",
    "        \n",
    "        while(l < len(l_arr)):\n",
    "            arr.append(l_arr[l])\n",
    "            l += 1\n",
    "        \n",
    "        while(r < len(r_arr)):\n",
    "            arr.append(r_arr[r])\n",
    "            r += 1\n",
    "        \n",
    "        return arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from bisect import bisect_right, bisect_left\n",
    "\n",
    "class BIT:\n",
    "  def __init__(self, n) -> None:\n",
    "    # 数组下标1开始为有效值\n",
    "    self.tree = [0] * (n + 1)\n",
    "  def update(self, i):\n",
    "    while i < len(self.tree):\n",
    "      self.tree[i] += 1\n",
    "      i += i & -i\n",
    "  def query(self, i):\n",
    "    ans = 0\n",
    "    while i > 0:\n",
    "      ans += self.tree[i]\n",
    "      i -= i & -i\n",
    "    return ans\n",
    "\n",
    "class Solution:\n",
    "  def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "    n = len(nums)\n",
    "    p = [0] * (n + 1)\n",
    "    for i, x in enumerate(nums):\n",
    "      p[i + 1] += p[i] + nums[i]\n",
    "    s = set(p)\n",
    "    b = sorted(s)\n",
    "    bit = BIT(len(b))\n",
    "    ans = 0\n",
    "    for x in p:\n",
    "      l = x - upper\n",
    "      r = x - lower\n",
    "      ans += bit.query(bisect_right(b, r)) - bit.query(bisect_left(b, l))\n",
    "      bit.update(bisect_left(b, x) + 1)\n",
    "    return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        \"\"\"\n",
    "        前缀和：prefix[i]: sum[0...i]\n",
    "        区间和：sum_range[i...j] = sum[i...j] = sum[0...j] - sum[0...i] + nums[i]\n",
    "                                 = prefix[j] - prefix[i] + nums[i]\n",
    "        \n",
    "        于是，对于区间 [lo...hi]：\n",
    "            lower <= sum_range[lo...hi] <= upper\n",
    "        即，\n",
    "            lower <= prefix[hi] - prefix[lo] + nums[lo] <= upper\n",
    "\n",
    "        对上述不等式变形，有：\n",
    "            prefix[hi] - upper <= prefix[lo] - nums[lo] <= prefix[hi] - lower\n",
    "\n",
    "        于是，我们可以用一个有序列表 sl 保存 prefix[lo] - nums[lo]，\n",
    "        枚举右端点 hi，使用二分查找，得到满足上述不等式的元素个数\n",
    "        注意有序列表 sl 中的元素是动态增加的，要确保区间端点 lo <= hi\n",
    "        \n",
    "        \"\"\"\n",
    "\n",
    "        n = len(nums)\n",
    "\n",
    "        prefix = [0 for _ in range(n)]\n",
    "        prefix[0] = nums[0]\n",
    "        for i in range(1, n):\n",
    "            prefix[i] = prefix[i - 1] + nums[i]\n",
    "\n",
    "        sl = SortedList()\n",
    "\n",
    "        res = 0\n",
    "\n",
    "        # 枚举区间右端点 hi\n",
    "        # prefix[lo] - nums[lo] <= prefix[hi] - lower\n",
    "        # prefix[lo] - nums[lo] >= prefix[hi] - upper\n",
    "        for i in range(n):\n",
    "            sl.add(prefix[i] - nums[i])\n",
    "            \n",
    "            right = sl.bisect_right(prefix[i] - lower)\n",
    "            left = sl.bisect_left(prefix[i] - upper)\n",
    "\n",
    "            res += right - left\n",
    "\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        n = len(nums)\n",
    "        RES = 0\n",
    "\n",
    "        def fR(o,l,r):\n",
    "            nonlocal RES\n",
    "            if l == r:return 0\n",
    "            m = (l+r)//2\n",
    "            res = 0;temp = 0\n",
    "            fR(2*o,l,m);fR(2*o+1,m+1,r)\n",
    "            C = Counter()\n",
    "            temp = 0\n",
    "            for i in range(m+1,r+1):\n",
    "                temp += nums[i]\n",
    "                C[temp] += 1\n",
    "            F = []\n",
    "            for a,b in C.items():\n",
    "                F.append([a,b])\n",
    "            F.sort()\n",
    "            for idx,(_,i) in enumerate(F):\n",
    "                if idx == 0:continue\n",
    "                F[idx][1] += F[idx-1][1]\n",
    "            temp = 0\n",
    "            for i in range(m,l-1,-1):\n",
    "                temp += nums[i]\n",
    "                p1 = bisect_left(F,lower-temp,key = lambda x:x[0])\n",
    "                a = F[p1-1][1] if p1 != 0 else 0\n",
    "                p2 = bisect_right(F,upper-temp,key = lambda x:x[0])\n",
    "                b = F[p2-1][1] if p2 != 0 else 0\n",
    "                res += b-a\n",
    "            RES += res\n",
    "            return res\n",
    "        fR(1,0,n-1) \n",
    "        return RES + sum([1 if lower <= i <= upper else 0 for i in nums])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    \n",
    "    def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:        \n",
    "        acc = list(accumulate(nums, initial=0))\n",
    "        n = len(nums)\n",
    "\n",
    "        prefix = [0 for _ in range(n)]\n",
    "        for i in range(1, n):\n",
    "            prefix[i] = prefix[i - 1] + nums[i]\n",
    "\n",
    "        sl = SortedList()\n",
    "\n",
    "        res = 0\n",
    "\n",
    "        # 枚举区间右端点 hi\n",
    "        # prefix[lo] - nums[lo] <= prefix[hi] - lower\n",
    "        # prefix[lo] - nums[lo] >= prefix[hi] - upper\n",
    "        for i in range(n):\n",
    "            sl.add(prefix[i] - nums[i])\n",
    "            \n",
    "            right = sl.bisect_right(prefix[i] - lower)\n",
    "            left = sl.bisect_left(prefix[i] - upper)\n",
    "\n",
    "            res += right - left\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        # 求前缀和\n",
    "        l = len(nums)+1\n",
    "        s = [0] * l\n",
    "        for i,n in enumerate(nums):\n",
    "            s[i+1] = s[i] + n\n",
    "        dst = [0] * len(s)\n",
    "\n",
    "        def merge_count_sort(nums,l,r):\n",
    "            # 统计个数之后再对对应的区间进行排序\n",
    "            if r-l<=1:\n",
    "                return 0\n",
    "            m = (l+r)//2\n",
    "            cnt1 = merge_count_sort(nums,l,m)\n",
    "            cnt2 = merge_count_sort(nums,m,r)\n",
    "            # count\n",
    "            # 区间和]i,j]的开始i [l,m[ 结束 j [m,r[\n",
    "            res = 0\n",
    "            r_lower,r_upper = m,m\n",
    "            for i in range(l,m):\n",
    "                while r_lower<r and nums[r_lower]-nums[i]<lower:\n",
    "                    r_lower += 1\n",
    "                if r_lower==r: # 后序的nums[i]值可能更大，所以nums[r_lower]-nums[i]只可能更小，即铁定<lower\n",
    "                    break\n",
    "                # nums[r_lower]-nums[i]>=lower\n",
    "                # r_upper = r_lower # 注意！ 这里r_upper只要从上次结束的位置往后移动即可。\n",
    "                while r_upper<r and nums[r_upper]-nums[i]<=upper:\n",
    "                    r_upper += 1\n",
    "                # [r_lower,r_upper[\n",
    "                res += r_upper-r_lower\n",
    "\n",
    "            # sort [l,r[\n",
    "            i,j = l,m\n",
    "            for k in range(l,r):\n",
    "                if j==r or (i<m and nums[i]<nums[j]):\n",
    "                    dst[k] = nums[i]\n",
    "                    i+=1\n",
    "                else:\n",
    "                    dst[k] = nums[j]\n",
    "                    j+=1\n",
    "            for k in range(l,r):\n",
    "                nums[k] = dst[k]\n",
    "            # nums[l:r] = sorted(nums[l:r])\n",
    "\n",
    "            # print(l,m,nums[l:m])\n",
    "            # print(m,r,nums[m:r])\n",
    "            # print(res,cnt1,cnt2)\n",
    "            # print(nums)\n",
    "            # print(dst)\n",
    "            # print('-'*10)\n",
    "            return res + cnt1 + cnt2\n",
    "\n",
    "        return merge_count_sort(s,0,len(s))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        \n",
    "\n",
    "        preSum = [0]\n",
    "\n",
    "        cur = 0\n",
    "        for n in nums:\n",
    "            cur += n\n",
    "            preSum.append(cur)\n",
    "        \n",
    "\n",
    "\n",
    "        def mergeSort(begin, end):\n",
    "            if begin >= end - 1:\n",
    "                return 0\n",
    "            \n",
    "            mid = begin + (end - begin) // 2\n",
    "            lRes = mergeSort(begin, mid)\n",
    "            rRes = mergeSort(mid, end)\n",
    "            res = lRes + rRes\n",
    "\n",
    "            i = begin \n",
    "            j = mid \n",
    "            k = mid\n",
    "            while i < mid:\n",
    "                \n",
    "                while j < end and preSum[j] - preSum[i] < lower:\n",
    "                    j += 1\n",
    "                while k < end and preSum[k] - preSum[i] <= upper:\n",
    "                    k += 1\n",
    "\n",
    "                res += k - j\n",
    "                i += 1\n",
    "            \n",
    "            tmp = []\n",
    "            l = begin \n",
    "            r = mid \n",
    "            while l < mid and r < end:\n",
    "                if preSum[l] <= preSum[r]:\n",
    "                    tmp.append(preSum[l])\n",
    "                    l += 1\n",
    "                else:\n",
    "                    tmp.append(preSum[r])\n",
    "                    r += 1\n",
    "            while l < mid:\n",
    "                tmp.append(preSum[l])\n",
    "                l += 1\n",
    "            while r < end:\n",
    "                tmp.append(preSum[r])\n",
    "                r += 1\n",
    "            for cur in range(len(tmp)):\n",
    "                preSum[begin + cur] = tmp[cur]\n",
    "            return res\n",
    "        #print(preSum)\n",
    "        res =  mergeSort(0, len(preSum))\n",
    "        #print(preSum)\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        n = len(nums)\n",
    "        global sums\n",
    "        global temp\n",
    "        sums = [0]*n\n",
    "        for ii in range(n):\n",
    "            sums[ii] = nums[ii]+(sums[ii-1] if ii>0 else 0)\n",
    "        temp = [0]*n\n",
    "        def merge(l,r):\n",
    "            global sums\n",
    "            global temp\n",
    "            if l>=r:return\n",
    "            mid = l+((r-l)>>1)\n",
    "            idx1 = l\n",
    "            idx2 = mid+1\n",
    "            idx = 0\n",
    "            while(idx1<=mid and idx2<=r):\n",
    "                if(sums[idx1]<sums[idx2]):\n",
    "                    temp[idx] = sums[idx1]\n",
    "                    idx1+=1\n",
    "                else:\n",
    "                    temp[idx] = sums[idx2]\n",
    "                    idx2+=1\n",
    "                idx+=1\n",
    "            while idx1<=mid:\n",
    "                temp[idx] = sums[idx1]\n",
    "                idx+=1\n",
    "                idx1+=1\n",
    "            while idx2<=r:\n",
    "                temp[idx] = sums[idx2]\n",
    "                idx+=1\n",
    "                idx2+=1\n",
    "            sums[l:r+1] = temp[0:idx]\n",
    "        def caculate(l,r):\n",
    "            global sums\n",
    "            if l>r:\n",
    "                return 0\n",
    "            if l==r:\n",
    "                return 1 if sums[l]>=lower and sums[l]<=upper else 0\n",
    "            ans = 0\n",
    "            mid = l+((r-l)>>1)\n",
    "            ans+=caculate(l, mid)\n",
    "            ans+=caculate(mid+1, r)\n",
    "            idx1 = l\n",
    "            idx21 = mid+1\n",
    "            idx22 = mid+1\n",
    "            while(idx1<=mid):\n",
    "                while idx21<=r and sums[idx21]-sums[idx1]<lower:\n",
    "                    idx21+=1\n",
    "                while idx22<=r and sums[idx22]-sums[idx1]<=upper:\n",
    "                    idx22+=1\n",
    "                ans+=(idx22-idx21)\n",
    "                idx1+=1\n",
    "            merge(l,r)\n",
    "            return ans\n",
    "        return caculate(0, n-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "#         helper = [0] * len(nums)\n",
    "#         helper[0] = nums[0]\n",
    "#         for i in range(1, len(nums)):\n",
    "#             helper[i] = helper[i-1] + nums[i]\n",
    "\n",
    "#         dp = [0] * len(nums)\n",
    "#         if nums[0] >= lower and nums[0] <= upper:\n",
    "#             dp[0] = 1\n",
    "        \n",
    "#         for i in range(1, len(nums)):\n",
    "#             dp[i] = dp[i-1]\n",
    "#             if helper[i] >= lower and helper[i] <= upper:\n",
    "#                 dp[i] += 1\n",
    "#             for ii in range(i):\n",
    "#                 if helper[i] - helper[ii] >= lower and helper[i] - helper[ii] <= upper:\n",
    "#                     dp[i] += 1\n",
    "\n",
    "#         return dp[-1] \n",
    "\n",
    "class Solution:\n",
    "    def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        def merge(a, b):\n",
    "            c = []\n",
    "\n",
    "            i = j = 0\n",
    "            for item in a:\n",
    "                while i < len(b) and b[i][0] > item[0] and b[i][1] - item[1] < lower:\n",
    "                    i += 1\n",
    "                while j < len(b) and b[j][0] > item[0] and b[j][1] - item[1] <= upper:\n",
    "                    j += 1\n",
    "                self.ans += (j - i)\n",
    "\n",
    "            i = j = 0 \n",
    "            while i < len(a) and j < len(b):\n",
    "                if a[i][1] < b[j][1]:\n",
    "                    c.append(a[i])\n",
    "                    i += 1\n",
    "                else:\n",
    "                    c.append(b[j])\n",
    "                    j += 1\n",
    "            c.extend(a[i:])\n",
    "            c.extend(b[j:])\n",
    "            return c\n",
    "        \n",
    "        def mergesort(a):\n",
    "            if len(a) <= 1:\n",
    "                return a\n",
    "            \n",
    "            left = mergesort(a[:len(a)//2])\n",
    "            right = mergesort(a[len(a)//2:])\n",
    "\n",
    "            return merge(left, right)\n",
    "        \n",
    "        self.ans = 0\n",
    "        if nums[0] >= lower and nums[0] <= upper:\n",
    "            self.ans += 1\n",
    "        for i in range(1, len(nums)):\n",
    "            nums[i] += nums[i-1]\n",
    "            if nums[i] >= lower and nums[i] <= upper:\n",
    "                self.ans += 1\n",
    "        nums_helper = list(enumerate(nums))\n",
    "        tmp = mergesort(nums_helper)\n",
    "\n",
    "        return self.ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def count_pre_sum(self, nums):\n",
    "        res = [0]\n",
    "        for num in nums:\n",
    "            res.append(res[-1] + num)\n",
    "        return res\n",
    "\n",
    "    def countRangeSum(self, nums: list[int], lower: int, upper: int) -> int:\n",
    "        prefix_sum = self.count_pre_sum(nums)\n",
    "        n = len(prefix_sum)\n",
    "\n",
    "        def merge_sort(left, right):\n",
    "            if left == right:\n",
    "                return 0\n",
    "            mid = left + (right - left) // 2\n",
    "            count = merge_sort(left, mid) + merge_sort(mid+1, right)\n",
    "            k = left\n",
    "            # i: lower bound. j: upper bound\n",
    "            i = j = mid + 1\n",
    "            while k < mid + 1:\n",
    "                while i <= right and prefix_sum[i] - prefix_sum[k] < lower:\n",
    "                    i += 1\n",
    "                while j <= right and prefix_sum[j] - prefix_sum[k] <= upper:\n",
    "                    j += 1\n",
    "                k += 1\n",
    "                count += j - i\n",
    "            prefix_sum[left: right+1] = sorted(prefix_sum[left: right+1])\n",
    "            return count\n",
    "        return merge_sort(0, n-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class BIT:\n",
    "    def __init__(self, n):\n",
    "        self.n = n\n",
    "        self.tree = [0] * (n + 1)\n",
    "\n",
    "    def add(self, idx: int, val: int):\n",
    "        while idx <= self.n:\n",
    "            self.tree[idx] += val\n",
    "            idx += idx & (-idx)\n",
    "\n",
    "    def query(self, idx: int):\n",
    "        res = 0\n",
    "        while idx:\n",
    "            res += self.tree[idx]\n",
    "            idx &= idx - 1\n",
    "        return res\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        n = len(nums)\n",
    "        pre_sum = [0] * (n + 1)\n",
    "        for i, val in enumerate(nums):\n",
    "            pre_sum[i + 1] = pre_sum[i] + val\n",
    "\n",
    "        temp_sum = list(set(pre_sum))\n",
    "        temp_sum.sort()\n",
    "        idx = {v: i for i, v in enumerate(temp_sum)}\n",
    "        tree = BIT(len(temp_sum))\n",
    "        tree.add(idx[0] + 1, 1)\n",
    "        ans = 0\n",
    "        for pre in pre_sum[1:]:\n",
    "            # 找排序后的temp_sum数组中在pre - upper和pre - lower之间的pre_sum的下标。\n",
    "            # 实际上temp_sum[up:low]范围内的pre_sum都能满足要求，\n",
    "            # 我们要求的是这个范围内的区间的总数量，\n",
    "            # 也就是满足pre - upper<=pre_sum[i]<=pre - lower的i的数量\n",
    "            # 因而在BIT中求的是区间和，假设满足上述条件最大的pre_sum在temp_sum数组中的下标为r，最小的下标为l\n",
    "            # 则需要的是BIT中截至r的前缀和减去l-1的前缀和，而从temp_sum的下标到BIT下标的转换需要+1，\n",
    "            # 所以刚好分别是bisect_left和bisect_right\n",
    "            up = bisect.bisect_left(temp_sum, pre - upper)\n",
    "            low = bisect.bisect_right(temp_sum, pre - lower)\n",
    "\n",
    "            ans += tree.query(low) - tree.query(up)\n",
    "            tree.add(idx[pre] + 1, 1)\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from bisect import bisect_right, bisect_left\n",
    "\n",
    "class BIT:\n",
    "  def __init__(self, n) -> None:\n",
    "    # 数组下标1开始为有效值\n",
    "    self.tree = [0] * (n + 1)\n",
    "  def update(self, i):\n",
    "    while i < len(self.tree):\n",
    "      self.tree[i] += 1\n",
    "      i += i & -i\n",
    "  def query(self, i):\n",
    "    ans = 0\n",
    "    while i > 0:\n",
    "      ans += self.tree[i]\n",
    "      i -= i & -i\n",
    "    return ans\n",
    "\n",
    "class Solution:\n",
    "  def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "    n = len(nums)\n",
    "    p = [0] * (n + 1)\n",
    "    for i, x in enumerate(nums):\n",
    "      p[i + 1] += p[i] + nums[i]\n",
    "    b = sorted(set(p))\n",
    "    hash = { x: i for i, x in enumerate(b) }\n",
    "    bit = BIT(len(b))\n",
    "    ans = 0\n",
    "    for x in p:\n",
    "      l = x - upper\n",
    "      r = x - lower\n",
    "      ans += bit.query(bisect_right(b, r)) - bit.query(bisect_left(b, l))\n",
    "      bit.update(hash[x] + 1)\n",
    "    return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import bisect\n",
    "class Solution:\n",
    "    def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        presum = [0]\n",
    "        for i in range(len(nums)):\n",
    "            presum.append(presum[-1]+nums[i])\n",
    "        nums = presum\n",
    "        n = len(nums)\n",
    "        self.tree = [0] * (n+1)\n",
    "        self.MAXN = n\n",
    "        lisan = [i for i in nums]\n",
    "        lisan = list(set(lisan))\n",
    "        lisan.sort()\n",
    "        val2id = {lisan[i]: i+1 for i in range(len(lisan))}\n",
    "        nums = [val2id[i] for i in nums]\n",
    "        self.modify(nums[0], 1)\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(1, n):\n",
    "            l = bisect.bisect_left(lisan, lisan[nums[i]-1]-upper) + 1\n",
    "            r = bisect.bisect_right(lisan, lisan[nums[i]-1]-lower)\n",
    "            ans += self.query(r) - self.query(l-1)\n",
    "            self.modify(nums[i], 1)\n",
    "        return ans\n",
    "\n",
    "\n",
    "    def modify(self, pos, val):\n",
    "        while pos <= self.MAXN:\n",
    "            self.tree[pos] += val\n",
    "            pos += Solution.lowbit(pos)\n",
    "\n",
    "    def query(self, pos):\n",
    "        ans = 0\n",
    "        while pos:\n",
    "            ans += self.tree[pos]\n",
    "            pos -= Solution.lowbit(pos)\n",
    "        return ans\n",
    "\n",
    "    def lowbit(x):\n",
    "        return x & (-x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        from sortedcontainers import SortedList\n",
    "        ans = 0\n",
    "        p = 0\n",
    "        # 前缀和 + SortedList, 枚举区间右端点\n",
    "        arr = SortedList()\n",
    "        for i in range(len(nums)):\n",
    "            p += nums[i]\n",
    "\n",
    "            # arr 中存的是[0, i]的区间和(i < j)\n",
    "            r = arr.bisect_right(p - lower)\n",
    "            l = arr.bisect_left(p - upper)\n",
    "            # print(arr, arr[l:r])\n",
    "            # (i, j] 区间和在 [lower, upper] 之间的个数为 l-r\n",
    "            ans += r - l\n",
    "\n",
    "            ans += p >= lower and p <= upper\n",
    "\n",
    "            arr.add(p)\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n",
    "class bit_tree:\n",
    "    def __init__(self, M, N):\n",
    "        self.M = M\n",
    "        self.sz = N - M + 1 + 1\n",
    "        self.arr = Counter()\n",
    "\n",
    "    def add(self, x, val):\n",
    "        idx = x - self.M + 1\n",
    "        assert idx > 0, \"\"\n",
    "        while idx < self.sz:\n",
    "            self.arr[idx] += val\n",
    "            idx += idx & -idx\n",
    "\n",
    "    def query(self, x):\n",
    "        idx = x - self.M + 1\n",
    "        assert idx > 0, \"\"\n",
    "        ans = 0\n",
    "        while idx > 0:\n",
    "            ans += self.arr[idx]\n",
    "            idx -= idx & -idx\n",
    "        return ans\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        \"\"\" 前缀和 + 树状数组 \"\"\"\n",
    "        n = len(nums)\n",
    "        total = sum(abs(x) for x in nums + [lower, upper, 1])\n",
    "        # print(total)\n",
    "        obj = bit_tree(-total, total)\n",
    "\n",
    "        ans, p = 0, 0\n",
    "        for i in range(n):\n",
    "            obj.add(p, 1)\n",
    "            p += nums[i]\n",
    "            cnt = obj.query(p - lower) - obj.query(p - upper - 1)\n",
    "            ans += cnt\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        \"\"\" 前缀和 + 树状数组 + 离散化 \"\"\"\n",
    "        n = len(nums)\n",
    "        prefix = list(itertools.accumulate(nums))\n",
    "        prefix_sort = list(sorted(set(prefix)))\n",
    "        prefix_sort = [-inf] + prefix_sort\n",
    "\n",
    "        ans = 0\n",
    "        obj = bit_tree(0, n+1)\n",
    "        for p in prefix:\n",
    "            # 由于这种离散化的方式是等价于, 在排序数组中, 根据相对偏移来查找范围 [prefix[i]-upper, prefix[i]-lower] 内前缀和的个数(以此作为左边界)\n",
    "            # 所以当前 prefix[i] 的 cnt 不能放进去, 不然在查找范围包括0时, 会多统计一个左边界\n",
    "\n",
    "            # cnt = obj.query(posi(p - lower)) - obj.query(posi(p - upper-1))\n",
    "            l = bisect_left(prefix_sort, p - upper) - 1\n",
    "            r = bisect_right(prefix_sort, p - lower) - 1\n",
    "            # print(\"range:{}, founded:{}\".format([p - upper, p - lower], prefix_sort[l+1:r+1]))\n",
    "            cnt = obj.query(r) - obj.query(l)\n",
    "            # print('now_prefix:', p, 'prefix', prefix)\n",
    "            # print('arr', {prefix_sort[i]: obj.query(i) - obj.query(i-1) for i in range(len(prefix_sort))})\n",
    "            # print('cnt', cnt)\n",
    "            ans += cnt\n",
    "            # 累加上[0,i]这个区间的结果\n",
    "            ans += p >= lower and p <= upper\n",
    "\n",
    "            obj.add(bisect_left(prefix_sort, p), 1)\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        # 前缀和\n",
    "        pre_sum = [0, nums[0]]\n",
    "        for idx in range(1, len(nums)):\n",
    "            pre_sum.append(nums[idx] + pre_sum[-1])\n",
    "        arr = []\n",
    "        self.res = 0\n",
    "        self.lower, self.upper = lower, upper\n",
    "        for idx, val in enumerate(pre_sum):\n",
    "            arr.append((idx, val))\n",
    "        new = self.merge_sort(arr)\n",
    "        # print(arr)\n",
    "        # print(new)\n",
    "        return self.res\n",
    "\n",
    "    def merge_sort(self, arr):\n",
    "        if len(arr) <= 1:\n",
    "            return arr\n",
    "        mid = len(arr) // 2\n",
    "        left = self.merge_sort(arr[:mid])\n",
    "        right = self.merge_sort(arr[mid:])\n",
    "        return self.merge(left, right)\n",
    "\n",
    "    def merge(self, left, right):\n",
    "        left_length, right_length = len(left), len(right)\n",
    "        # 计算满足条件的数据\n",
    "        start, end = 0, 0\n",
    "        for idx in range(left_length):\n",
    "            while start < right_length and right[start][1] - left[idx][1] < self.lower:\n",
    "                start += 1\n",
    "            while end < right_length and right[end][1] - left[idx][1] <= self.upper:\n",
    "                end += 1\n",
    "            self.res += (end - start)\n",
    "        # 归并排序\n",
    "        left_idx, right_idx = 0, 0\n",
    "        arr = []\n",
    "        while left_idx < left_length and right_idx < right_length:\n",
    "            if left[left_idx][1] <= right[right_idx][1]:\n",
    "                arr.append(left[left_idx])\n",
    "                left_idx += 1\n",
    "            else:\n",
    "                arr.append(right[right_idx])\n",
    "                right_idx += 1\n",
    "        while left_idx < left_length:\n",
    "            arr.append(left[left_idx])\n",
    "            left_idx += 1\n",
    "        while right_idx < right_length:\n",
    "            arr.append(right[right_idx])\n",
    "            right_idx += 1\n",
    "        return arr\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        n = len(nums)\n",
    "        RES = 0\n",
    "        def fR(o,l,r):\n",
    "            nonlocal RES\n",
    "            if l == r:return 0\n",
    "            m = (l+r)//2\n",
    "            res = 0;temp = 0\n",
    "            fR(2*o,l,m);fR(2*o+1,m+1,r)\n",
    "            F = []\n",
    "            temp = 0\n",
    "            for i in range(m+1,r+1):\n",
    "                temp += nums[i]\n",
    "                F.append(temp)\n",
    "            F.sort()\n",
    "            temp = 0\n",
    "            for i in range(m,l-1,-1):\n",
    "                temp += nums[i]\n",
    "                p1 = bisect_left(F,lower-temp)\n",
    "                p2 = bisect_right(F,upper-temp)\n",
    "                res += p2-p1\n",
    "            RES += res\n",
    "            return res\n",
    "        fR(1,0,n-1) \n",
    "        return RES + sum([1 if lower <= i <= upper else 0 for i in nums])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import bisect\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        pre_sum = [0]\n",
    "        for num in nums:\n",
    "            pre_sum.append(pre_sum[-1] + num)\n",
    "\n",
    "        # 离散化\n",
    "        map = {}\n",
    "        unique_list = sorted(list(set(pre_sum)))\n",
    "        for index, val in enumerate(unique_list):\n",
    "            map[val] = index + 1\n",
    "\n",
    "        # 建树状数组，记录每个元素的个数\n",
    "        bit = BIT(len(map))\n",
    "\n",
    "        # 元素先全部加入树状数组\n",
    "        for num in pre_sum:\n",
    "            bit.add(map[num], 1)\n",
    "        \n",
    "        res = 0\n",
    "        for val in pre_sum:\n",
    "            # 取出元素\n",
    "            bit.add(map[val], -1)\n",
    "            # 确定查找范围\n",
    "            left = bisect.bisect_left(unique_list, lower + val)\n",
    "            right = bisect.bisect_right(unique_list, upper + val)\n",
    "            res += bit.query(right) - bit.query(left)        \n",
    "        return res\n",
    "\n",
    "class BIT:\n",
    "    def __init__(self, sz: int):\n",
    "        self.size = sz\n",
    "        self.tree = [0] * (sz + 1)\n",
    "\n",
    "    def add(self, x: int, val: int):\n",
    "        i = x\n",
    "        while i <= self.size:\n",
    "            self.tree[i] += val\n",
    "            i += self.lowbit(i)\n",
    "\n",
    "    def query(self, x: int) -> int:\n",
    "        res = 0\n",
    "        i = x\n",
    "        while i > 0:\n",
    "            res += self.tree[i]\n",
    "            i -= self.lowbit(i)\n",
    "        return res\n",
    "\n",
    "    def lowbit(self, x: int) -> int:\n",
    "        return x & -x\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "\n",
    "        n = len(nums)\n",
    "        prefix = 0\n",
    "        prefix_set = set([0])\n",
    "        prefix_index_dict = {}\n",
    "\n",
    "        for num in nums:\n",
    "            prefix+= num\n",
    "            prefix_set.add(num)\n",
    "            prefix_set.add(prefix)\n",
    "        \n",
    "        prefix_list = sorted(list(prefix_set))\n",
    "        for i ,n in enumerate(prefix_list):\n",
    "            prefix_index_dict[n] = i+1\n",
    "        \n",
    "        tree_nodes = [0]*(len(prefix_list)+1)\n",
    "\n",
    "        def low_bit(x):\n",
    "            return x & -x\n",
    "\n",
    "        def add(index:int):\n",
    "            while index<len(tree_nodes):\n",
    "                tree_nodes[index] += 1\n",
    "                index += low_bit(index)\n",
    "        \n",
    "        def rangeSum(index:int)->int:\n",
    "            ret = 0\n",
    "            # print(index,tree_nodes)\n",
    "            while index>0:\n",
    "                ret += tree_nodes[index]\n",
    "                index -= low_bit(index)\n",
    "            return ret\n",
    "        \n",
    "        prefix = 0\n",
    "        res = 0\n",
    "        # index = bisect.bisect_left(prefix_list,0)\n",
    "        add(prefix_index_dict[0])\n",
    "        # print(prefix_list)\n",
    "        for num in nums:\n",
    "            prefix += num\n",
    "            \n",
    "            low_val , up_val = prefix - upper,prefix - lower\n",
    "\n",
    "            # if low_val>prefix_list[-1] or up_val< prefix_list[0]:\n",
    "            #     add(prefix_index_dict[prefix])\n",
    "            #     continue\n",
    "\n",
    "            index0 = bisect.bisect_left(prefix_list,low_val)\n",
    "            index1 = bisect.bisect_left(prefix_list,up_val)\n",
    "\n",
    "            if index1<len(prefix_list) and up_val == prefix_list[index1]:\n",
    "                index1+=1\n",
    "\n",
    "            # index1 = min(len(tree_nodes)-1,index1+1)\n",
    "\n",
    "            # if index0 == index1 and (num > upper or num< lower):\n",
    "            #     add(prefix_index_dict[prefix])\n",
    "            #     continue\n",
    "         \n",
    "            cnt = rangeSum(index1) - rangeSum(index0)\n",
    "            # print(prefix,index1 , index0,low_val , up_val,tree_nodes, rangeSum(index1), rangeSum(index0))\n",
    "            res += cnt\n",
    "            add(prefix_index_dict[prefix])\n",
    "        \n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRangeSum(self, nums, lower: int, upper: int):\n",
    "        n = len(nums)\n",
    "        def f(left, right):\n",
    "            if right == left: return 1 if (nums[left]>=lower and nums[left]<=upper) else 0\n",
    "\n",
    "            mid = (left + right) // 2\n",
    "            ans = f(left, mid) + f(mid+1, right)\n",
    "            current = 0\n",
    "            lsum = []\n",
    "            for i in range(mid, left-1, -1):\n",
    "                current += nums[i]\n",
    "                lsum.append(current)\n",
    "            current = 0\n",
    "            rsum = []\n",
    "            for i in range(mid+1, right+1, 1):\n",
    "                current += nums[i]\n",
    "                rsum.append(current)\n",
    "            lsum.sort()\n",
    "            rsum.sort()\n",
    "            hi = len(rsum) - 1\n",
    "            lo = len(rsum)\n",
    "            for sum in lsum:\n",
    "                margin = upper - sum\n",
    "                while hi >= 0 and rsum[hi] > margin:\n",
    "                    hi -= 1\n",
    "                margin = lower - sum\n",
    "                lo = min(lo, hi+1)\n",
    "                while lo > 0 and rsum[lo-1]>=margin:\n",
    "                    lo -= 1\n",
    "                ans += max(0, hi - lo + 1)\n",
    "            return ans\n",
    "        return f(0, n-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        res = 0\n",
    "        for i in range(1, len(nums)):\n",
    "            nums[i] = nums[i] + nums[i-1]\n",
    "        def countMerge(beg, mid, end, lst = nums):\n",
    "            nonlocal res\n",
    "            if end == beg:\n",
    "                res += int(lst[beg] >= lower and lst[end] <= upper)\n",
    "                return\n",
    "            left = mid + 1\n",
    "            right = mid + 1\n",
    "            for ind in range(beg, mid+1):\n",
    "                while left <= end and lst[ind] + lower > lst[left]:\n",
    "                    left += 1\n",
    "                while right <= end and lst[ind] + upper >= lst[right]:\n",
    "                    right += 1\n",
    "                if left > end:\n",
    "                    break\n",
    "                res += right - left\n",
    "            mlst = []\n",
    "            left = beg\n",
    "            right = mid + 1\n",
    "            while left <= mid and right <= end:\n",
    "                if lst[left] <= lst[right]:\n",
    "                    mlst.append(lst[left])\n",
    "                    left += 1\n",
    "                else:\n",
    "                    mlst.append(lst[right])\n",
    "                    right += 1\n",
    "            while left <= mid:\n",
    "                mlst.append(lst[left])\n",
    "                left += 1\n",
    "            while right <= end:\n",
    "                mlst.append(lst[right])\n",
    "                right += 1\n",
    "            for i in range(len(mlst)):\n",
    "                lst[beg + i] = mlst[i]\n",
    "        \n",
    "        def Msort(beg, end, lst = nums):\n",
    "            mid = (beg + end) // 2\n",
    "            if end == beg:\n",
    "                countMerge(beg, mid, end, lst)\n",
    "            else:\n",
    "                Msort(beg, mid, lst)\n",
    "                Msort(mid + 1, end, lst)\n",
    "                countMerge(beg, mid, end, lst)\n",
    "        \n",
    "        Msort(0, len(nums) - 1, nums)\n",
    "        return res\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRangeSum(self, numss, lower: int, upper: int) -> int:\n",
    "        pre = [0]\n",
    "        for num in numss:\n",
    "            pre.append(pre[-1] + num)\n",
    "        def calc_pre(nums,lower,upper,left,right):\n",
    "            if left == right:\n",
    "                return 0\n",
    "            m = (left + right) // 2\n",
    "            l = calc_pre(nums,lower,upper,left,m)\n",
    "            r = calc_pre(nums,lower,upper,m + 1,right)\n",
    "            ans = l + r\n",
    "\n",
    "            start,l1,r1 = left, m + 1, m + 1\n",
    "            while start <= m:\n",
    "                while l1 <= right and nums[l1] - nums[start] < lower:\n",
    "                    l1 += 1\n",
    "                while r1 <= right and nums[r1] - nums[start] <= upper:\n",
    "                    r1 += 1\n",
    "                ans += (r1 - l1)\n",
    "                start += 1\n",
    "\n",
    "            temp = [0] * (right - left + 1)\n",
    "            ll, rr =left, m + 1\n",
    "            p = 0\n",
    "            while ll <= m or rr <= right:\n",
    "                if (ll > m):\n",
    "                    temp[p] = nums[rr]\n",
    "                    rr += 1\n",
    "                elif rr > right:\n",
    "                    temp[p] = nums[ll]\n",
    "                    ll += 1\n",
    "                else:\n",
    "                    if nums[ll] < nums[rr]:\n",
    "                        temp[p] = nums[ll]\n",
    "                        ll += 1\n",
    "                    else:\n",
    "                        temp[p] = nums[rr]\n",
    "                        rr += 1\n",
    "                p += 1\n",
    "\n",
    "            for i in range(len(temp)):\n",
    "                pre[i + left] = temp[i]\n",
    "\n",
    "            return ans\n",
    "\n",
    "        return calc_pre(pre,lower,upper,0,len(pre) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        \"\"\"\n",
    "        优化暴力法，双层循环可以使用双指针、哈希表、分治、单调栈等方法优化\n",
    "        由于数组无序，无法使用双指针，且窗口不易确定，无法使用滑动窗口。\n",
    "        无法确定一个固定的值，无法使用哈希表，\n",
    "        我们尝试使用分治法来解决，可以使用归并排序的方式来解决，确定两个有序数组的差值满足 [lower,upper] 可以在 O(N) 范围内\n",
    "        :param nums:\n",
    "        :param lower:\n",
    "        :param upper:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        summary = [0]\n",
    "        length = len(nums)\n",
    "        for i in range(length):\n",
    "            summary.append(summary[-1] + nums[i])\n",
    "        summary = summary[1:]\n",
    "\n",
    "        def merge(start: int, mid: int, end: int) -> int:\n",
    "            \"\"\"\n",
    "            合并两个有序数组，同时返回两个有序数组的差满足 [lower,upper] 的个数\n",
    "            :param mid:\n",
    "            :param start:\n",
    "            :param end:\n",
    "            :return:\n",
    "            \"\"\"\n",
    "            j_0 = mid + 1\n",
    "            j_1 = mid + 1\n",
    "            res = 0\n",
    "            for i in range(start, mid + 1):\n",
    "                while j_0 <= end:\n",
    "                    if summary[j_0] - summary[i] < lower:\n",
    "                        j_0 += 1\n",
    "                    else:\n",
    "                        break\n",
    "                while j_1 <= end:\n",
    "                    if summary[j_1] - summary[i] <= upper:\n",
    "                        j_1 += 1\n",
    "                    else:\n",
    "                        break\n",
    "                j_1 = min(end, j_1)\n",
    "                j_0 = min(end, j_0)\n",
    "                if summary[j_0] - summary[i] >= lower and j_0 <= j_1:\n",
    "                    if summary[j_1] - summary[i] <= upper:\n",
    "                        res += j_1 - j_0 + 1\n",
    "                    else:\n",
    "                        res += j_1 - j_0\n",
    "\n",
    "                # res += j_1 - j_0 + 1 if j_1 <= end and j_0 <= end else 0\n",
    "            collect = []\n",
    "            i, j = start, mid + 1\n",
    "            while i <= mid or j <= end:\n",
    "                if i <= mid and j <= end:\n",
    "                    if summary[i] < summary[j]:\n",
    "                        collect.append(summary[i])\n",
    "                        i += 1\n",
    "                    else:\n",
    "                        collect.append(summary[j])\n",
    "                        j += 1\n",
    "                elif i <= mid:\n",
    "                    collect.append(summary[i])\n",
    "                    i += 1\n",
    "                elif j <= end:\n",
    "                    collect.append(summary[j])\n",
    "                    j += 1\n",
    "            summary[start:end + 1] = collect\n",
    "            return res\n",
    "\n",
    "        def find(start: int, end: int) -> int:\n",
    "            if start == end:\n",
    "                if lower <= summary[start] <= upper:\n",
    "                    return 1\n",
    "                else:\n",
    "                    return 0\n",
    "            if start > end:\n",
    "                return 0\n",
    "            mid = (start + end) // 2\n",
    "            left = find(start, mid)\n",
    "            right = find(mid + 1, end)\n",
    "            merge_res = merge(start, mid, end)\n",
    "            return left + right + merge_res\n",
    "\n",
    "        return find(0, length - 1)\n",
    "\n",
    "    def countRangeSum_0(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        \"\"\"\n",
    "        暴力法：时间复杂度：O(N^2)\n",
    "        空间复杂度：O(N)\n",
    "        :param nums:\n",
    "        :param lower:\n",
    "        :param upper:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        summary = [0]\n",
    "        length = len(nums)\n",
    "        for i in range(length):\n",
    "            summary.append(summary[-1] + nums[i])\n",
    "        res = 0\n",
    "        for i in range(length + 1):\n",
    "            for j in range(i + 1, length + 1):\n",
    "                if lower <= summary[j] - summary[i] <= upper:\n",
    "                    res += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        n=len(nums)\n",
    "        pre=[0]*(n+1)\n",
    "        for i in range(n):\n",
    "            pre[i+1]=pre[i]+nums[i]\n",
    "        res=0\n",
    "        def sort(l,r):\n",
    "            if l>=r:\n",
    "                return \n",
    "            mid=(l+r)//2\n",
    "            sort(l,mid)\n",
    "            sort(mid+1,r)\n",
    "            merge(l,mid,r)\n",
    "        def merge(l,mid,r):\n",
    "            nonlocal res\n",
    "            start,end=mid+1,mid+1\n",
    "            for i in range(l,mid+1):\n",
    "                while start<=r and pre[start]-pre[i]<lower:\n",
    "                    start+=1\n",
    "                while end<=r and pre[end]-pre[i]<=upper:\n",
    "                    end+=1\n",
    "                res+=end-start\n",
    "            i,j=l,mid+1\n",
    "            tmp=[]\n",
    "            while i<=mid or j<=r:\n",
    "                if i>mid:\n",
    "                    tmp.append(pre[j])\n",
    "                    j+=1\n",
    "                elif j>r:\n",
    "                    tmp.append(pre[i])\n",
    "                    i+=1\n",
    "                else:\n",
    "                    if pre[i]>pre[j]:\n",
    "                        tmp.append(pre[j])\n",
    "                        j+=1\n",
    "                    else:\n",
    "                        tmp.append(pre[i])\n",
    "                        i+=1\n",
    "            pre[l:r+1]=tmp\n",
    "        sort(0,n)\n",
    "        return res\n",
    "        \n",
    "            \n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        \"\"\"\n",
    "        由于数组中元素有正有负导致无法确定滑动窗口的限制窗口的条件，所以无法用滑动窗口来优化。\n",
    "        我们知道两个有序数组我们可以通过双指针来确定他们的差等于一个 target 的组合有多少\n",
    "        所以也就能确定范围在 lower upper 之间的组合数有多少\n",
    "        :param nums:\n",
    "        :param lower:\n",
    "        :param upper:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        summary = []\n",
    "        length = len(nums)\n",
    "        res = 0\n",
    "        for i in range(length):\n",
    "            if i == 0:\n",
    "                tmp = nums[0]\n",
    "            else:\n",
    "                tmp = summary[-1] + nums[i]\n",
    "            if lower <= tmp <= upper:\n",
    "                res += 1\n",
    "            summary.append(tmp)\n",
    "\n",
    "        def merge_sort(start: int, end: int) -> int:\n",
    "            if start >= end:\n",
    "                return 0\n",
    "\n",
    "            def merge(start: int, mid: int, end: int) -> int:\n",
    "                # 将两个有序数组进行对比获取符合 [lower, upper] 的组合\n",
    "                merge_res = 0\n",
    "                i, j = mid + 1, mid + 1\n",
    "                for x in range(start, mid + 1):\n",
    "                    while i <= end and summary[i] - summary[x] < lower:\n",
    "                        i += 1\n",
    "                    while j <= end and summary[j] - summary[x] <= upper:\n",
    "                        j += 1\n",
    "                    merge_res += j - i\n",
    "                # 合并两个有序数组\n",
    "                l = start\n",
    "                r = mid + 1\n",
    "                tmp = []\n",
    "                while l <= mid or r <= end:\n",
    "                    if l <= mid and r <= end:\n",
    "                        if summary[l] < summary[r]:\n",
    "                            tmp.append(summary[l])\n",
    "                            l += 1\n",
    "                        else:\n",
    "                            tmp.append(summary[r])\n",
    "                            r += 1\n",
    "                    elif l <= mid:\n",
    "                        tmp.append(summary[l])\n",
    "                        l += 1\n",
    "                    elif r <= end:\n",
    "                        tmp.append(summary[r])\n",
    "                        r += 1\n",
    "                for i in range(start, end + 1):\n",
    "                    summary[i] = tmp[i - start]\n",
    "                return merge_res\n",
    "\n",
    "            mid = (start + end) // 2\n",
    "            left_res = merge_sort(start, mid)\n",
    "            right_res = merge_sort(mid + 1, end)\n",
    "            merge_res = merge(start, mid, end)\n",
    "            # print(summary)\n",
    "            return left_res + right_res + merge_res\n",
    "\n",
    "        return res + merge_sort(0, length - 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        # 求前缀和\n",
    "        l = len(nums)+1\n",
    "        s = [0] * l\n",
    "        for i,n in enumerate(nums):\n",
    "            s[i+1] = s[i] + n\n",
    "        dst = [0] * len(s)\n",
    "\n",
    "        def merge_count_sort(nums,l,r,lower,upper):\n",
    "            # 统计个数之后再对对应的区间进行排序\n",
    "            if r-l<=1:\n",
    "                return 0\n",
    "            m = (l+r)//2\n",
    "            cnt1 = merge_count_sort(nums,l,m,lower,upper)\n",
    "            cnt2 = merge_count_sort(nums,m,r,lower,upper)\n",
    "            # count\n",
    "            # 区间和]i,j]的开始i [l,m[ 结束 j [m,r[\n",
    "            res = 0\n",
    "            r_lower,r_upper = m,m\n",
    "            for i in range(l,m):\n",
    "                while r_lower<r and nums[r_lower]-nums[i]<lower:\n",
    "                    r_lower += 1\n",
    "                if r_lower==r: # 后序的nums[i]值可能更大，所以nums[r_lower]-nums[i]只可能更小，即铁定<lower\n",
    "                    break\n",
    "                # nums[r_lower]-nums[i]>=lower\n",
    "                # r_upper = r_lower # 注意！ 这里r_upper只要从上次结束的位置往后移动即可。\n",
    "                while r_upper<r and nums[r_upper]-nums[i]<=upper:\n",
    "                    r_upper += 1\n",
    "                # [r_lower,r_upper[\n",
    "                res += r_upper-r_lower\n",
    "\n",
    "            # sort [l,r[\n",
    "            i,j = l,m\n",
    "            for k in range(l,r):\n",
    "                if j==r or (i<m and nums[i]<nums[j]):\n",
    "                    dst[k] = nums[i]\n",
    "                    i+=1\n",
    "                else:\n",
    "                    dst[k] = nums[j]\n",
    "                    j+=1\n",
    "            for k in range(l,r):\n",
    "                nums[k] = dst[k]\n",
    "            # nums[l:r] = sorted(nums[l:r])\n",
    "\n",
    "            # print(l,m,nums[l:m])\n",
    "            # print(m,r,nums[m:r])\n",
    "            # print(res,cnt1,cnt2)\n",
    "            # print(nums)\n",
    "            # print(dst)\n",
    "            # print('-'*10)\n",
    "            return res + cnt1 + cnt2\n",
    "\n",
    "        return merge_count_sort(s,0,len(s),lower,upper)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        prev_sum = [0]\n",
    "        for num in nums:\n",
    "            prev_sum.append(prev_sum[-1] + num)\n",
    "        tmp = [0] * len(prev_sum)\n",
    "\n",
    "        def merge_sort(left, right):\n",
    "            if left >= right:\n",
    "                return 0\n",
    "            \n",
    "            mid = left + (right - left) // 2\n",
    "            left_cnt = merge_sort(left, mid)\n",
    "            right_cnt = merge_sort(mid+1, right)\n",
    "\n",
    "            j = mid + 1\n",
    "            k = mid + 1\n",
    "            cnt = 0\n",
    "            for i in range(left, mid+1):\n",
    "                while j <= right and prev_sum[j] - prev_sum[i] < lower:\n",
    "                    j += 1\n",
    "                while k <= right and prev_sum[k] - prev_sum[i] <= upper:\n",
    "                    k += 1\n",
    "                cnt += (k - j)\n",
    "            \n",
    "            i, j = left, mid+1\n",
    "            k = left\n",
    "            while i <= mid and j <= right:\n",
    "                if prev_sum[i] <= prev_sum[j]:\n",
    "                    tmp[k] = prev_sum[i]\n",
    "                    i += 1\n",
    "                else:\n",
    "                    tmp[k] = prev_sum[j]\n",
    "                    j += 1\n",
    "                k += 1\n",
    "            while i <= mid:\n",
    "                tmp[k] = prev_sum[i]\n",
    "                k += 1\n",
    "                i += 1\n",
    "            while j <= right:\n",
    "                tmp[k] = prev_sum[j]\n",
    "                k += 1\n",
    "                j += 1\n",
    "            prev_sum[left:right+1] = tmp[left:right+1]\n",
    "            return left_cnt + right_cnt + cnt\n",
    "\n",
    "        return merge_sort(0, len(prev_sum)-1)        \n",
    "        \n",
    "            \n",
    "            \n",
    "            \n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        n = len(nums)\n",
    "        presum = [0] * (n + 1)\n",
    "        for i in range(1, n + 1):\n",
    "            presum[i] = presum[i - 1] + nums[i - 1]\n",
    "\n",
    "        tmp = [0] * (n + 1)\n",
    "\n",
    "        def merge(l, r):\n",
    "            if l >= r: return 0\n",
    "            m = (l + r) >> 1\n",
    "            ans = merge(l, m) + merge(m + 1, r)\n",
    "\n",
    "            j = m + 1\n",
    "            cnt = 0\n",
    "            # s[i] > s[j] - lo的多少？\n",
    "            for i in range(l, m + 1):\n",
    "                while j <= r and presum[i] > presum[j] - lower:\n",
    "                    j += 1\n",
    "                cnt += j - m - 1\n",
    "\n",
    "            # s[j] > s[i] + up的多少？\n",
    "            i = l\n",
    "            for j in range(m + 1, r + 1):\n",
    "                while i <= m and presum[j] > presum[i] + upper:\n",
    "                    i += 1\n",
    "                cnt += i - l\n",
    "\n",
    "            ans += (m - l + 1) * (r - m) - cnt\n",
    "\n",
    "            for i in range(l, r + 1):\n",
    "                tmp[i] = presum[i]\n",
    "\n",
    "            i, j, idx = l, m + 1, l\n",
    "            while i <= m or j <= r:\n",
    "                # 左边用尽\n",
    "                if i > m:\n",
    "                    presum[idx] = tmp[j]\n",
    "                    j += 1\n",
    "                elif j > r:\n",
    "                    presum[idx] = tmp[i]\n",
    "                    i += 1\n",
    "                elif tmp[i] <= tmp[j]:\n",
    "                    presum[idx] = tmp[i]\n",
    "                    i += 1\n",
    "                else:\n",
    "                    presum[idx] = tmp[j]\n",
    "                    j += 1\n",
    "                idx += 1\n",
    "\n",
    "            return ans\n",
    "\n",
    "        return merge(0, n)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class SbtNode:\n",
    "    def __init__(self, key):\n",
    "        self.key = key\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "        self.size = 1\n",
    "        self.all = 1\n",
    "\n",
    "\n",
    "class SizeBalancedTreeSet:\n",
    "    def __init__(self):\n",
    "        self.root = None\n",
    "        self.sets = set()\n",
    "\n",
    "    def right_rotate(self, cur):\n",
    "        cur_node_num = cur.all - (cur.left.all if cur.left is not None else 0) - (cur.right.all if cur.right is not None else 0)\n",
    "        left = cur.left\n",
    "        cur.left = left.right\n",
    "        left.right = cur\n",
    "        left.size = cur.size\n",
    "        cur.size = (cur.left.size if cur.left is not None else 0) + (cur.right.size if cur.right is not None else 0) + 1\n",
    "        left.all = cur.all\n",
    "        cur.all = (cur.left.all if cur.left is not None else 0) + (cur.right.all if cur.right is not None else 0) + cur_node_num\n",
    "        return left\n",
    "\n",
    "    def left_rotate(self, cur):\n",
    "        cur_node_num = cur.all - (cur.left.all if cur.left is not None else 0) - (cur.right.all if cur.right is not None else 0)\n",
    "        right = cur.right\n",
    "        cur.right = right.left\n",
    "        right.left = cur\n",
    "        right.size = cur.size\n",
    "        cur.size = (cur.left.size if cur.left is not None else 0) + (cur.right.size if cur.right is not None else 0) + 1\n",
    "        right.all = cur.all\n",
    "        cur.all = (cur.left.all if cur.left is not None else 0) + (cur.right.all if cur.right is not None else 0) + cur_node_num\n",
    "        return right\n",
    "\n",
    "    def maintain(self, cur):\n",
    "        if cur is None:\n",
    "            return None\n",
    "        left_size = cur.left.size if cur.left is not None else 0\n",
    "        left_left_size = cur.left.left.size if cur.left is not None and cur.left.left is not None else 0\n",
    "        left_right_size = cur.left.right.size if cur.left is not None and cur.left.right is not None else 0\n",
    "        right_size = cur.right.size if cur.right is not None else 0\n",
    "        right_right_size = cur.right.right.size if cur.right is not None and cur.right.right is not None else 0\n",
    "        right_left_size = cur.right.left.size if cur.right is not None and cur.right.left is not None else 0\n",
    "        if left_left_size > right_size:\n",
    "            cur = self.right_rotate(cur)\n",
    "            cur.right = self.maintain(cur.right)\n",
    "            cur = self.maintain(cur)\n",
    "        elif left_right_size > right_size:\n",
    "            cur.left = self.left_rotate(cur.left)\n",
    "            cur = self.right_rotate(cur)\n",
    "            cur.left = self.maintain(cur.left)\n",
    "            cur.right = self.maintain(cur.right)\n",
    "            cur = self.maintain(cur)\n",
    "        elif right_right_size > left_size:\n",
    "            cur = self.left_rotate(cur)\n",
    "            cur.left = self.maintain(cur.left)\n",
    "            cur = self.maintain(cur)\n",
    "        elif right_left_size > left_size:\n",
    "            cur.right = self.right_rotate(cur.right)\n",
    "            cur = self.left_rotate(cur)\n",
    "            cur.left = self.maintain(cur.left)\n",
    "            cur.right = self.maintain(cur.right)\n",
    "            cur = self.maintain(cur)\n",
    "        return cur\n",
    "\n",
    "    def add_num(self, sum):\n",
    "        contains = sum in self.sets\n",
    "        self.root = self.add(self.root, sum, contains)\n",
    "        self.sets.add(sum)\n",
    "\n",
    "    def add(self, cur, key, contains):\n",
    "        if cur is None:\n",
    "            return SbtNode(key)\n",
    "        else:\n",
    "            cur.all += 1\n",
    "            if key == cur.key:\n",
    "                return cur\n",
    "            else:\n",
    "                if contains is False:\n",
    "                    cur.size += 1\n",
    "                if key < cur.key:\n",
    "                    cur.left = self.add(cur.left, key, contains)\n",
    "                else:\n",
    "                    cur.right = self.add(cur.right, key, contains)\n",
    "                return self.maintain(cur)\n",
    "\n",
    "    def less_key_size(self, key):\n",
    "        cur = self.root\n",
    "        ans = 0\n",
    "        while cur is not None:\n",
    "            if key == cur.key:\n",
    "                return ans + (cur.left.all if cur.left is not None else 0)  # 等于的时候左边的要加进来\n",
    "            elif key < cur.key:\n",
    "                cur = cur.left\n",
    "            else:\n",
    "                ans += cur.all - (cur.right.all if cur.right is not None else 0)\n",
    "                cur = cur.right\n",
    "        return ans\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countRangeSum(self, nums: List[int], lower: int, upper: int):\n",
    "        tree_set = SizeBalancedTreeSet()\n",
    "        sum = 0\n",
    "        ans = 0\n",
    "        tree_set.add_num(0)\n",
    "        for i in range(len(nums)):\n",
    "            sum += nums[i]\n",
    "            a = tree_set.less_key_size(sum - lower + 1)\n",
    "            b = tree_set.less_key_size(sum - upper)\n",
    "            ans += a - b\n",
    "            tree_set.add_num(sum)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        pre_sum = [0] * (len(nums) + 1)\n",
    "        for i in range(len(nums)):\n",
    "            pre_sum[i + 1] = nums[i] + pre_sum[i]\n",
    "        \n",
    "        n = len(pre_sum)\n",
    "        tmp = [0] * n\n",
    "        self.cnt = 0\n",
    "\n",
    "        def merge_sort(nums, lo, hi):\n",
    "            if lo >= hi:\n",
    "                return\n",
    "            mid = (lo + hi) // 2\n",
    "            merge_sort(nums, lo, mid)\n",
    "            merge_sort(nums, mid + 1, hi)\n",
    "            merge(nums, lo, mid, hi)\n",
    "\n",
    "        def merge(nums, lo, mid, hi):\n",
    "            for i in range(lo, hi + 1):\n",
    "                tmp[i] = nums[i]\n",
    "            start = end = mid + 1\n",
    "            for i in range(lo, mid + 1):\n",
    "                while start <= hi and nums[start] - nums[i] < lower:\n",
    "                    start += 1\n",
    "                while end <= hi and nums[end] - nums[i] <= upper:\n",
    "                    end += 1\n",
    "                self.cnt += end - start\n",
    "\n",
    "            i, j = lo, mid + 1\n",
    "            for p in range(lo, hi + 1):\n",
    "                if i == mid + 1:\n",
    "                    nums[p] = tmp[j]\n",
    "                    j += 1\n",
    "                elif j == hi + 1 or tmp[i] <= tmp[j]:\n",
    "                    nums[p] = tmp[i]\n",
    "                    i += 1\n",
    "                else:\n",
    "                    nums[p] = tmp[j]\n",
    "                    j += 1\n",
    "            \n",
    "        merge_sort(pre_sum, 0, n - 1)\n",
    "        return self.cnt "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        pre = [0]\n",
    "        for x in nums: pre.append(pre[-1]+x)\n",
    "        #print('pre =',pre)\n",
    "        def count(a,b) -> int:\n",
    "            #print('a,b =',a,b)\n",
    "            if b-a == 1: return 0\n",
    "            m = (a+b)//2\n",
    "            n_range = count(a,m) + count(m,b)\n",
    "            x0 = pre[a:m]\n",
    "            x1 = pre[m:b]\n",
    "            i = j = 0\n",
    "            for x in x0:\n",
    "                while i < b-m and x1[i] < x+lower: i += 1\n",
    "                while j < b-m and x1[j] <= x+upper: j += 1\n",
    "                n_range += j-i\n",
    "            i = j = 0\n",
    "            while i < m-a or j < b-m:\n",
    "                if j == b-m or i < m-a and j < b-m and x0[i] < x1[j]:\n",
    "                    pre[a+i+j] = x0[i]\n",
    "                    i += 1\n",
    "                else:\n",
    "                    pre[a+i+j] = x1[j]\n",
    "                    j += 1\n",
    "            #print(pre[a:b],n_range)\n",
    "            return n_range\n",
    "        return count(0,len(pre))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        n = len(nums)\n",
    "        pre_sums = [0] + list(itertools.accumulate(nums))\n",
    "\n",
    "        def merge(i: int, j: int) -> int:\n",
    "\n",
    "            if i >= j:\n",
    "                return 0\n",
    "\n",
    "            mid = (i + j) // 2\n",
    "            l = merge(i, mid)\n",
    "            r = merge(mid + 1, j)\n",
    "            ret = l + r\n",
    "\n",
    "            a, b = mid + 1, mid + 1\n",
    "            x = i\n",
    "            x1, x2 = 0, 0\n",
    "            while x <= mid:\n",
    "                while a <= j and pre_sums[a] - pre_sums[x] < lower:\n",
    "                    a += 1\n",
    "                    x1 += 1\n",
    "\n",
    "                while b <= j and pre_sums[b] - pre_sums[x] <= upper:\n",
    "                    x2 += 1\n",
    "                    b += 1\n",
    "\n",
    "                ret += x2 - x1\n",
    "                x += 1\n",
    "            pre_sums[i: j + 1] = sorted(pre_sums[i: j + 1])\n",
    "            return ret\n",
    "\n",
    "        ans = merge(0, n)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        n = len(nums)\n",
    "        s = [0] * (n + 1)\n",
    "        alls = []\n",
    "        alls.append(0)\n",
    "        for i in range(1, n + 1):\n",
    "            s[i] = s[i - 1] + nums[i - 1]\n",
    "            alls.append(s[i])\n",
    "            alls.append(s[i] - lower)\n",
    "            alls.append(s[i] - upper)\n",
    "        alls = sorted(list(set(alls)))\n",
    "        fen = FenwickTree(len(alls) + 2)\n",
    "        def q(x): return bisect.bisect_left(alls, x) + 1 \n",
    "        res = 0\n",
    "        for i in range(0, n + 1): \n",
    "            L = q(s[i] - lower)\n",
    "            R = q(s[i] - upper) \n",
    "            res += fen.rsum(R, L)\n",
    "            fen.add(q(s[i]), 1)\n",
    "        return res \n",
    "class FenwickTree:\n",
    "    def __init__(self, n):\n",
    "        self.tr = [0] * n\n",
    "    def add(self, x, v):\n",
    "        while x < len(self.tr):\n",
    "            self.tr[x] += v\n",
    "            x += x & -x\n",
    "    def query(self, x):\n",
    "        res = 0\n",
    "        while x > 0:\n",
    "            res += self.tr[x]\n",
    "            x -= x & -x\n",
    "        return res\n",
    "    def rsum(self, l, r):\n",
    "        return self.query(r) - self.query(l - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        n = len(nums)\n",
    "        presum = [0] * (n+1)\n",
    "        temp = [0] * (n+1)\n",
    "        self.cnt = 0\n",
    "        for i in range(n):\n",
    "            presum[i+1] = presum[i] + nums[i]\n",
    "\n",
    "        def merge(lo,mid,hi):\n",
    "            for i in range(lo,hi+1):\n",
    "                temp[i] = presum[i]\n",
    "\n",
    "            l = mid+1\n",
    "            r = mid+1\n",
    "        # start = end = mid + 1\n",
    "        # for i in range(lo, mid + 1):\n",
    "        #     # 如果 nums[i] 对应的区间是 [start, end)，\n",
    "        #     # 那么 nums[i+1] 对应的区间一定会整体右移，类似滑动窗口\n",
    "        #     while start <= hi and nums[start] - nums[i] < self.lower:\n",
    "        #         start += 1\n",
    "        #     while end <= hi and nums[end] - nums[i] <= self.upper:\n",
    "        #         end += 1\n",
    "        #     self.count += end - start\n",
    "            for i in range(lo,mid+1):\n",
    "                # temp[j] - temp[i] in [lower,upper]\n",
    "                # temp[j] < upper + temp[i]\n",
    "                # temp[j] > lower + temp[i]\n",
    "                while l <= hi and temp[l]-temp[i] < lower:\n",
    "                    l += 1\n",
    "                while r <= hi and temp[r]-temp[i] <= upper:\n",
    "                    r += 1\n",
    "                self.cnt += r-l\n",
    "\n",
    "            x = lo\n",
    "            i = lo\n",
    "            j = mid + 1\n",
    "\n",
    "            while x <= hi:\n",
    "                if i == mid + 1:\n",
    "                    presum[x] = temp[j]\n",
    "                    j += 1\n",
    "                elif j == hi + 1:\n",
    "                    presum[x] = temp[i]\n",
    "                    i += 1\n",
    "                elif temp[i] < temp[j]:\n",
    "                    presum[x] = temp[i]\n",
    "                    i += 1\n",
    "                else:\n",
    "                    presum[x] = temp[j]\n",
    "                    j += 1\n",
    "                x += 1\n",
    "            \n",
    "\n",
    "        def sort(lo,hi):\n",
    "            if lo >= hi:\n",
    "                return\n",
    "            mid = lo + (hi-lo)//2\n",
    "            sort(lo,mid)\n",
    "            sort(mid+1,hi)\n",
    "            merge(lo,mid,hi)\n",
    "            return\n",
    "        # print(presum)\n",
    "        sort(0,n)\n",
    "        # print(presum)\n",
    "        return self.cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        n = len(nums)\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        \n",
    "        self.ans = 0\n",
    "\n",
    "        pre_sum = [0] * (1 + n)\n",
    "        pre_sum[0] = 0   # presum[j] - presum[i] = sum(num[i:j])\n",
    "        for i in range(1, n + 1):\n",
    "            pre_sum[i] = pre_sum[i-1] + nums[i - 1]\n",
    "        \n",
    "        tmp = [0] * (n+1)\n",
    "        def sort(arr, left, right):\n",
    "            if left >= right:\n",
    "                return \n",
    "\n",
    "            mid = (left + right) // 2\n",
    "            sort(arr, left, mid)\n",
    "            sort(arr, mid + 1, right)\n",
    "\n",
    "            merge(arr, left, mid, right)\n",
    "        \n",
    "        def merge(arr, left, mid, right):\n",
    "            end = mid + 1\n",
    "            start = mid + 1\n",
    "\n",
    "            for i in range(left, mid + 1):\n",
    "                while start <= right and pre_sum[start] - pre_sum[i] < lower:\n",
    "                    start += 1\n",
    "\n",
    "                while end <= right and pre_sum[end] - pre_sum[i] <= upper:\n",
    "                    end += 1\n",
    "                \n",
    "                self.ans += end - start\n",
    "\n",
    "            idx = left\n",
    "            i, j = left, mid + 1\n",
    "\n",
    "            while i <= mid and j <= right:\n",
    "                if arr[i] <= arr[j]:\n",
    "                    tmp[idx] = arr[i]\n",
    "                    i += 1\n",
    "                else:\n",
    "                    tmp[idx] = arr[j]\n",
    "                    j += 1\n",
    "                idx += 1\n",
    "\n",
    "            while i <= mid:\n",
    "                tmp[idx] = arr[i]\n",
    "                i += 1\n",
    "                idx += 1\n",
    "\n",
    "            while j <= right:\n",
    "                tmp[idx] = arr[j]\n",
    "                idx += 1\n",
    "                j += 1\n",
    "            \n",
    "            arr[left:right+ 1] = tmp[left:right+ 1]\n",
    "        \n",
    "        sort(pre_sum, 0, n)\n",
    "        return self.ans\n",
    "        \n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        arr=[0]\n",
    "        for i in nums:\n",
    "            arr.append(arr[-1]+i)\n",
    "        crr=[None]*(len(arr))\n",
    "        self.res=0\n",
    "        def cdq(s,e):\n",
    "            if s==e:\n",
    "                return \n",
    "            mid=(s+e)//2\n",
    "            cdq(s,mid);cdq(mid+1,e)\n",
    "            que=deque()\n",
    "            i=s;j=mid+1\n",
    "            while j<=e:\n",
    "                while i<=mid and arr[j]-arr[i]>=lower:\n",
    "                    que.append(i)\n",
    "                    i+=1\n",
    "                while que and arr[j]-arr[que[0]]>upper:\n",
    "                    que.popleft()\n",
    "                self.res+=len(que)\n",
    "                j+=1\n",
    "            i=s;j=mid+1;k=s\n",
    "            while i<=mid and j<=e:\n",
    "                if arr[i]<arr[j]:\n",
    "                    crr[k]=arr[i]\n",
    "                    i+=1;k+=1\n",
    "                else:\n",
    "                    crr[k]=arr[j]\n",
    "                    j+=1;k+=1\n",
    "            while i<=mid:\n",
    "                crr[k]=arr[i]\n",
    "                i+=1;k+=1\n",
    "            while j<=e:\n",
    "                crr[k]=arr[j]\n",
    "                j+=1;k+=1\n",
    "            for i in range(s,e+1):\n",
    "                arr[i]=crr[i]\n",
    "        cdq(0,len(arr)-1)\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:\r\n",
    "        pre_sum = [0] * (len(nums) + 1)\r\n",
    "        for i in range(0, len(nums)):\r\n",
    "            pre_sum[i+1] = pre_sum[i] + nums[i]\r\n",
    "\r\n",
    "        temp = pre_sum.copy()\r\n",
    "        count = [0] * len(pre_sum)\r\n",
    "\r\n",
    "        def merge(nums, lo, mid, hi):\r\n",
    "            temp[lo:hi+1] = nums[lo:hi+1]\r\n",
    "\r\n",
    "            start, end = mid+1, mid+1\r\n",
    "            for i in range(lo, mid+1):\r\n",
    "                while start < hi+1 and nums[start] - nums[i] < lower:\r\n",
    "                    start += 1\r\n",
    "                while end < hi+1 and nums[end] - nums[i] <= upper:\r\n",
    "                    end += 1\r\n",
    "                count[i] += (end - start)\r\n",
    "\r\n",
    "            i, j = lo, mid+1\r\n",
    "            for p in range(lo, hi+1):\r\n",
    "                if i == mid+1:\r\n",
    "                    nums[p] = temp[j]\r\n",
    "                    j += 1\r\n",
    "                elif j == hi+1:\r\n",
    "                    nums[p] = temp[i]\r\n",
    "                    i += 1\r\n",
    "                elif temp[i] < temp[j]:\r\n",
    "                    nums[p] = temp[i]\r\n",
    "                    i += 1\r\n",
    "                else:\r\n",
    "                    nums[p] = temp[j]\r\n",
    "                    j += 1\r\n",
    "\r\n",
    "        def mysort(nums, lo, hi):\r\n",
    "            if lo == hi:\r\n",
    "                return\r\n",
    "\r\n",
    "            mid = lo + (hi - lo) // 2\r\n",
    "            mysort(nums, lo, mid)\r\n",
    "            mysort(nums, mid+1, hi)\r\n",
    "            merge(nums, lo, mid, hi)\r\n",
    "        \r\n",
    "        mysort(pre_sum, 0, len(pre_sum)-1)\r\n",
    "        return sum(count)\r\n",
    "            \r\n",
    "            \r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        S={\"left\":None, \"right\":None, \"values\":[0, 1, 1]}\n",
    "        s=0\n",
    "        ret=0\n",
    "        def search(v, root):\n",
    "            if root is None:\n",
    "                return 0\n",
    "            if v<=root[\"values\"][0]:\n",
    "                ret=search(v, root[\"left\"])\n",
    "                if root[\"right\"] is not None:\n",
    "                    ret+=root[\"right\"][\"values\"][1]\n",
    "                return ret+1\n",
    "            else:\n",
    "                return search(v, root[\"right\"])\n",
    "                \n",
    "        def insert(v, root):\n",
    "            if root is None:\n",
    "                return {\"left\":None, \"right\":None, \"values\":[v, 1, 1]}\n",
    "            root[\"values\"][1]+=1\n",
    "            if v<=root[\"values\"][0]:\n",
    "                root[\"left\"]=insert(v, root[\"left\"])                   \n",
    "            else:\n",
    "                root[\"right\"]=insert(v, root[\"right\"])\n",
    "            ## balance\n",
    "            lnum=0 if root[\"left\"] is None else root[\"left\"][\"values\"][2]\n",
    "            rnum=0 if root[\"right\"] is None else root[\"right\"][\"values\"][2]\n",
    "            root[\"values\"][2]=max(lnum, rnum)+1\n",
    "            if lnum-rnum>1:\n",
    "                tmp=root[\"left\"]\n",
    "                root[\"left\"]=tmp[\"right\"]\n",
    "                tmp[\"right\"]=root\n",
    "\n",
    "                tnum=0 if root[\"left\"] is None else root[\"left\"][\"values\"][2]\n",
    "                tsize=0 if root[\"left\"] is None else root[\"left\"][\"values\"][1]\n",
    "                rsize=0 if root[\"right\"] is None else root[\"right\"][\"values\"][1]\n",
    "                tlsize=0 if tmp[\"left\"] is None else tmp[\"left\"][\"values\"][1]\n",
    "                root[\"values\"][2]=max(rnum, tnum)+1\n",
    "                root[\"values\"][1]=tsize+rsize+1\n",
    "                tmp[\"values\"][2]=max(tmp[\"values\"][2], tmp[\"right\"][\"values\"][2]+1)\n",
    "                tmp[\"values\"][1]=tlsize+tsize+rsize+2\n",
    "                root=tmp\n",
    "            elif rnum-lnum>1:\n",
    "                tmp=root[\"right\"]\n",
    "                root[\"right\"]=tmp[\"left\"]\n",
    "                tmp[\"left\"]=root\n",
    "\n",
    "                tnum=0 if root[\"right\"] is None else root[\"right\"][\"values\"][2]\n",
    "                tsize=0 if root[\"left\"] is None else root[\"left\"][\"values\"][1]\n",
    "                rsize=0 if root[\"right\"] is None else root[\"right\"][\"values\"][1]\n",
    "                tlsize=0 if tmp[\"right\"] is None else tmp[\"right\"][\"values\"][1]\n",
    "                root[\"values\"][2]=max(lnum, tnum)+1\n",
    "                root[\"values\"][1]=tsize+rsize+1\n",
    "                tmp[\"values\"][2]=max(tmp[\"values\"][2], tmp[\"left\"][\"values\"][2]+1)\n",
    "                tmp[\"values\"][1]=tlsize+tsize+rsize+2\n",
    "                root=tmp\n",
    "            return root\n",
    "        \n",
    "        for v in nums:\n",
    "            s+=v\n",
    "            lidx, uidx=s-lower+1, s-upper\n",
    "            lidx, uidx=search(lidx, S), search(uidx, S)\n",
    "            ret+=uidx-lidx\n",
    "            S=insert(s, S)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:\r\n",
    "        pre_sum = [0] * (len(nums) + 1)\r\n",
    "        for i in range(0, len(nums)):\r\n",
    "            pre_sum[i+1] = pre_sum[i] + nums[i]\r\n",
    "\r\n",
    "        temp = pre_sum.copy()\r\n",
    "        count = [0] * len(pre_sum)\r\n",
    "\r\n",
    "        def merge(nums, lo, mid, hi):\r\n",
    "            temp[lo:hi+1] = nums[lo:hi+1]\r\n",
    "\r\n",
    "            start, end = mid+1, mid+1\r\n",
    "            for i in range(lo, mid+1):\r\n",
    "                while start < hi+1 and nums[start] - nums[i] < lower:\r\n",
    "                    start += 1\r\n",
    "                while end < hi+1 and nums[end] - nums[i] <= upper:\r\n",
    "                    end += 1\r\n",
    "                count[i] += (end - start)\r\n",
    "\r\n",
    "            i, j = lo, mid+1\r\n",
    "            for p in range(lo, hi+1):\r\n",
    "                if i == mid+1:\r\n",
    "                    nums[p] = temp[j]\r\n",
    "                    j += 1\r\n",
    "                elif j == hi+1:\r\n",
    "                    nums[p] = temp[i]\r\n",
    "                    i += 1\r\n",
    "                elif temp[i] < temp[j]:\r\n",
    "                    nums[p] = temp[i]\r\n",
    "                    i += 1\r\n",
    "                else:\r\n",
    "                    nums[p] = temp[j]\r\n",
    "                    j += 1\r\n",
    "\r\n",
    "        def mysort(nums, lo, hi):\r\n",
    "            if lo == hi:\r\n",
    "                return\r\n",
    "\r\n",
    "            mid = lo + (hi - lo) // 2\r\n",
    "            mysort(nums, lo, mid)\r\n",
    "            mysort(nums, mid+1, hi)\r\n",
    "            merge(nums, lo, mid, hi)\r\n",
    "        \r\n",
    "        mysort(pre_sum, 0, len(pre_sum)-1)\r\n",
    "        print(pre_sum)\r\n",
    "        return sum(count)\r\n",
    "            \r\n",
    "            \r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class IntervalTree:\n",
    "    def __init__(self, size):\n",
    "        self.size = size\n",
    "        self.interval_tree = [0 for _ in range(size*4)]\n",
    "\n",
    "    def insert(self,p,l,r,index):\n",
    "        if index < l or r < index:\n",
    "            return \n",
    "        interval_tree = self.interval_tree        \n",
    "        if l == r:\n",
    "            interval_tree[p] += 1\n",
    "            return\n",
    "        mid = (l+r)//2\n",
    "        if index <= mid:\n",
    "            self.insert(p*2,l,mid,index)\n",
    "        else:\n",
    "            self.insert(p*2+1,mid+1,r,index)\n",
    "        interval_tree[p] = interval_tree[p*2]+interval_tree[p*2+1]       \n",
    "    \n",
    "    def query(self,p,l,r,x,y):\n",
    "        if y < l or r < x:\n",
    "            return 0\n",
    "        if x<=l and r<=y:\n",
    "            return self.interval_tree[p]\n",
    "        mid = (l+r)//2\n",
    "        s = 0\n",
    "        if x <= mid:\n",
    "            s += self.query(p*2,l,mid,x,y)\n",
    "        if mid < y:\n",
    "            s += self.query(p*2+1,mid+1,r,x,y)\n",
    "        return s\n",
    "\n",
    "class Solution:\n",
    "    def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:         \n",
    "        s = list(accumulate(nums,initial=0))\n",
    "        hashes = s + [ x-lower for x in s] + [ x-upper for x in s]\n",
    "        hashes = sorted(list(set(hashes)))\n",
    "        # 生成前缀和，问题转化为，对于每个j，找左边的i,判断 s[j]-upper<=s[i]<=s[j]-lower,统计这些i的数量\n",
    "        # 把所有前缀和数组中的数字插入线段树，并对这些数字划分区间，线段树维护当前区间数字数量，\n",
    "        # 所以需要对这些数字都散列化\n",
    "        tree_size = len(hashes)\n",
    "        tree = IntervalTree(tree_size)\n",
    "        cnt = 0\n",
    "        for i in s:\n",
    "            x = bisect_left(hashes,i-upper)\n",
    "            y = bisect_left(hashes,i-lower)\n",
    "            j = bisect_left(hashes,i)\n",
    "            c = tree.query(1,1,tree_size, x+1,y+1)\n",
    "            # print(x,y,j,c)\n",
    "            cnt += c\n",
    "            tree.insert(1,1,tree_size,j+1)\n",
    "\n",
    "        return cnt\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        import numpy as np\n",
    "        nums = list(np.cumsum(nums))\n",
    "        nums.insert(0, 0)\n",
    "        tmp = nums.copy()\n",
    "        count = 0\n",
    "\n",
    "        def sort(nums, lo, hi):\n",
    "            if lo == hi:\n",
    "                return\n",
    "            mid = lo + (hi - lo) // 2\n",
    "            sort(nums, lo, mid)\n",
    "            sort(nums, mid + 1, hi)\n",
    "            merge(nums, lo, mid, hi)\n",
    "\n",
    "        def merge(nums, lo, mid, hi):\n",
    "            nonlocal count\n",
    "            tmp[lo:hi + 1] = nums[lo:hi + 1]\n",
    "            start = mid + 1\n",
    "            end = mid + 1\n",
    "            for i in range(lo, mid + 1):\n",
    "                while start <= hi and nums[start] - nums[i] < lower :\n",
    "                    start += 1\n",
    "                while end <= hi and nums[end] - nums[i] <= upper :\n",
    "                    end += 1\n",
    "                count += end - start\n",
    "            i = lo\n",
    "            j = mid + 1\n",
    "            for p in range(lo, hi + 1):\n",
    "                if i == mid + 1:\n",
    "                    nums[p] = tmp[j]\n",
    "                    j += 1\n",
    "                elif j == hi + 1:\n",
    "                    nums[p] = tmp[i]\n",
    "                    i += 1\n",
    "                elif tmp[i] <= tmp[j]:\n",
    "                    nums[p] = tmp[i]\n",
    "                    i += 1\n",
    "                else:\n",
    "                    nums[p] = tmp[j]\n",
    "                    j += 1\n",
    "\n",
    "        sort(nums,0, len(nums) - 1)\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        #数状数组\n",
    "        he = [0]*(len(nums) + 1)\n",
    "\n",
    "        for i, n in enumerate(nums, 1):\n",
    "            he[i] = he[i - 1] + n\n",
    "\n",
    "        hec = {}\n",
    "        for one in he:\n",
    "            hec[one] = 0\n",
    "            hec[one + lower] = 0\n",
    "            hec[one + upper] = 0\n",
    "\n",
    "        l = list(hec)\n",
    "        l.sort()\n",
    "        for i, one in enumerate(l, 1):\n",
    "            hec[one] = i\n",
    "        del l\n",
    "\n",
    "        class BT:\n",
    "            # 从1开始\n",
    "            def __init__(self, n):\n",
    "                self.l = [0] * (n + 1)\n",
    "                self.n = n\n",
    "\n",
    "            def add(self, i, v):\n",
    "                while i <= self.n:\n",
    "                    self.l[i] += v\n",
    "                    i += i&(-i)\n",
    "\n",
    "            def get(self, i):\n",
    "                ret = 0\n",
    "                while i:\n",
    "                    ret += self.l[i]\n",
    "                    i -= i&(-i)\n",
    "                return ret\n",
    "\n",
    "        root = BT(len(hec))\n",
    "        ret = 0\n",
    "\n",
    "        for v in reversed(he):\n",
    "            ret += root.get(hec[v + upper]) - root.get(hec[v + lower] - 1)\n",
    "            root.add(hec[v], 1)\n",
    "\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import bisect\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class BIT:\n",
    "    def __init__(self, n: int):\n",
    "        self.n = n\n",
    "        self.tree = [0] * (n + 1)\n",
    "\n",
    "    def _low_bit(self, i: int) -> int:\n",
    "        return i & -i\n",
    "\n",
    "    def update(self, index: int, delta: int = 1):\n",
    "        while index <= self.n:\n",
    "            self.tree[index] += delta\n",
    "            index += self._low_bit(index)\n",
    "\n",
    "    def query(self, index: int) -> int:\n",
    "        total = 0\n",
    "        while index > 0:\n",
    "            total += self.tree[index]\n",
    "            index -= self._low_bit(index)\n",
    "        return total\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        n = len(nums)\n",
    "        pre_sum = [0] * (n + 1)\n",
    "        for i in range(1, n + 1):\n",
    "            pre_sum[i] = nums[i - 1] + pre_sum[i - 1]\n",
    "        all_num = set()\n",
    "        for num in pre_sum:\n",
    "            all_num.update((num - upper, num - lower, num))\n",
    "        all_num = sorted(all_num)\n",
    "        # 对前缀和数组做离散化处理\n",
    "        all_seq = {s: bisect.bisect_left(all_num, s) + 1 for s in all_num}\n",
    "        bit_tree = BIT(len(all_seq))\n",
    "        ans = 0\n",
    "        for i in range(n + 1):\n",
    "            left, right = all_seq[pre_sum[i] - upper] - 1, all_seq[pre_sum[i] - lower]\n",
    "            ans += bit_tree.query(right) - bit_tree.query(left)\n",
    "            bit_tree.update(all_seq[pre_sum[i]])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        N = len(nums)\n",
    "\n",
    "        ss = [0] + list(accumulate(nums, operator.add))\n",
    "\n",
    "        # 离散化\n",
    "        uss = set()\n",
    "        for s in ss:\n",
    "            uss.add(s)\n",
    "            uss.add(s-upper)\n",
    "            uss.add(s-lower)\n",
    "        uss = list(uss)\n",
    "        uss.sort()\n",
    "        M = len(uss)\n",
    "        s2i = dict()\n",
    "        for i, s in enumerate(uss):\n",
    "            s2i[s] = i\n",
    "\n",
    "        # xs = [-2, 5, -1]\n",
    "        # ss = [-2, 3, 2, 0]\n",
    "        # 考虑 [i, j] 需满足 lower <= ss[j] - ss[i-1] <= upper\n",
    "        # 以 j 为右端点的区间个数 = i 的个数，其满足\n",
    "        # 1. i <= j\n",
    "        # 2. lower - ss[j] <= -ss[i-1] <= upper - ss[j]\n",
    "        #    => ss[j] - upper <= ss[i-1] <= ss[j] - lower\n",
    "        # 等价于 [ss[j] - upper, ss[j] - lower] 的元素个数\n",
    "        tree = [0] * (M+1)\n",
    "        def lowbit(i):\n",
    "            return i & -i\n",
    "        def _add(i, v):\n",
    "            while i <= M:\n",
    "                tree[i] += v\n",
    "                i += lowbit(i)\n",
    "        def _query(i):\n",
    "            ans = 0\n",
    "            while i > 0:\n",
    "                ans += tree[i]\n",
    "                i -= lowbit(i)\n",
    "            return ans\n",
    "        def add(s):\n",
    "            _add(s2i[s]+1, 1)\n",
    "        def query(l, r):\n",
    "            return _query(s2i[r]+1) - _query(s2i[l])\n",
    "\n",
    "        ans = 0\n",
    "        for s in ss:\n",
    "            ans += query(s-upper, s-lower)\n",
    "            add(s)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class BIT:\n",
    "    def __init__(self, n: int):\n",
    "        self.n = n\n",
    "        self.tree = [0] * (n + 1)\n",
    "    \n",
    "    @staticmethod\n",
    "    def lowbit(x: int) -> int:\n",
    "        return x & (-x)\n",
    "    \n",
    "    def update(self, x: int, d: int):\n",
    "        while x <= self.n:\n",
    "            self.tree[x] += d\n",
    "            x += BIT.lowbit(x)\n",
    "    \n",
    "    def query(self, x: int) -> int:\n",
    "        ans = 0\n",
    "        while x > 0:\n",
    "            ans += self.tree[x]\n",
    "            x -= BIT.lowbit(x)\n",
    "        return ans\n",
    "\n",
    "class Solution:\n",
    "    def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        preSum = [0]\n",
    "        for n in nums:\n",
    "            preSum.append(preSum[-1] + n)\n",
    "        possibleNums = set()\n",
    "        for x in preSum:\n",
    "            possibleNums.add(x)\n",
    "            possibleNums.add(x - upper)\n",
    "            possibleNums.add(x - lower)\n",
    "        possibleNums = sorted(list(possibleNums))\n",
    "        lookup = {n : i for i, n in enumerate(possibleNums)}\n",
    "        bit = BIT(len(possibleNums))\n",
    "\n",
    "        ans = 0\n",
    "        for x in preSum:\n",
    "            l, r = lookup[x - upper], lookup[x - lower]\n",
    "            ans += bit.query(r + 1) - bit.query(l)\n",
    "            bit.update(lookup[x] + 1, 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class BitTree:          #树状数组 动态前缀和\n",
    "    def __init__(self, n):\n",
    "        self.tree = [0 for x in range(n + 1)]\n",
    "        self.n = n\n",
    "    #---- 最右侧1的权重\n",
    "    def lowbit(self, i: int) -> int:\n",
    "        return i & (-i)\n",
    "    #----某个位置，加上k\n",
    "    def update(self, i: int, k: int) -> None:\n",
    "        while i <= self.n:\n",
    "            self.tree[i] += k\n",
    "            i += self.lowbit(i)\n",
    "    #----前缀和（实指）   \n",
    "    def presum(self, i: int) -> int:\n",
    "        res = 0\n",
    "        while i > 0:\n",
    "            res += self.tree[i]\n",
    "            i -= self.lowbit(i)\n",
    "        return res\n",
    "\n",
    "class Solution:\n",
    "    def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        n = len(nums)\n",
    "        #---- 前缀和 实指\n",
    "        presum = [0 for _ in range(n + 1)]\n",
    "        for i in range(n):   #虚指\n",
    "            presum[i+1] = presum[i] + nums[i]\n",
    "            #------------------ 以presum 为对象  离散化 + 树状数组----------------------#\n",
    "        #------ 所有的点\n",
    "        all_num = []\n",
    "        for x in presum:\n",
    "            all_num += [x, x - lower, x - upper]\n",
    "        \n",
    "        #------ 离散化\n",
    "        #all_num = list(set(all_num))    #离散化，要去重 都行\n",
    "        all_num.sort()                  #排序\n",
    "\n",
    "        val_id = dict()\n",
    "        for i, x in enumerate(all_num):\n",
    "            val_id[x] = i\n",
    "        #------ 树状数组\n",
    "        BIT = BitTree(len(all_num))\n",
    "        res = 0\n",
    "        for i, x in enumerate(presum): #遍历，往前探\n",
    "            idL = val_id[x - upper]\n",
    "            idR = val_id[x - lower]\n",
    "            print(i,x,idL)\n",
    "            res +=  ( BIT.presum(idR + 1) - BIT.presum(idL + 1 - 1) )\n",
    "\n",
    "            ID = val_id[x]\n",
    "            BIT.update(ID + 1, 1)\n",
    "    \n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        i2v = set([0])\n",
    "        prefix = 0\n",
    "        for v in nums:\n",
    "            prefix += v\n",
    "            i2v.add(prefix)\n",
    "            i2v.add(prefix-lower)\n",
    "            i2v.add(prefix-upper-1)\n",
    "        i2v = list(i2v)\n",
    "        i2v.sort()\n",
    "        v2i = {}\n",
    "        for i, v in enumerate(i2v):\n",
    "            v2i[v] = i\n",
    "        \n",
    "        bit = [0] * (len(i2v) + 1)\n",
    "        \n",
    "        def update(i, v):\n",
    "            i += 1\n",
    "            while i < len(bit):\n",
    "                bit[i] += v\n",
    "                i += (i & (-i))\n",
    "        \n",
    "        def query(i):\n",
    "            i += 1\n",
    "            ret = 0\n",
    "            while i > 0:\n",
    "                ret += bit[i]\n",
    "                i -= (i & (-i))\n",
    "            return ret\n",
    "        \n",
    "        result = 0\n",
    "        update(v2i[0], 1)\n",
    "        prefix = 0\n",
    "        for v in nums:\n",
    "            prefix += v\n",
    "            result += query(v2i[prefix-lower]) - query(v2i[prefix-upper-1])\n",
    "            update(v2i[prefix], 1)\n",
    "        return result\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    class TreeArray:\n",
    "\n",
    "        def __init__(self, n):\n",
    "            self.n = n\n",
    "            self.c = [0] * (n + 1)\n",
    "\n",
    "        def lowbit(self, x):\n",
    "            return x & -x\n",
    "\n",
    "        def add(self, idx, x):\n",
    "            while idx <= self.n:\n",
    "                self.c[idx] += x\n",
    "                idx += self.lowbit(idx)\n",
    "        \n",
    "        def getsum(self, idx):\n",
    "            res = 0\n",
    "            while idx > 0:\n",
    "                res += self.c[idx]\n",
    "                idx -= self.lowbit(idx)\n",
    "            \n",
    "            return res\n",
    "\n",
    "    def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        allnum = set()\n",
    "        allnum.add(0)\n",
    "        s = 0\n",
    "        for x in nums:\n",
    "            s += x\n",
    "            allnum.add(s)\n",
    "            allnum.add(s - lower)\n",
    "            allnum.add(s - upper)\n",
    "        \n",
    "        allnum = list(allnum)\n",
    "        allnum.sort()\n",
    "\n",
    "        valus = {}\n",
    "        total = 0\n",
    "        for x in allnum:\n",
    "            total += 1\n",
    "            valus[x] = total\n",
    "        \n",
    "        treeArr = Solution.TreeArray(total)\n",
    "\n",
    "        res = 0\n",
    "        s = 0\n",
    "        treeArr.add(valus[s], 1)\n",
    "\n",
    "        for n in nums:\n",
    "            s += n\n",
    "            a = valus.get(s - lower)\n",
    "            b = valus.get(s - upper) - 1\n",
    "\n",
    "            res += treeArr.getsum(a) - treeArr.getsum(b)\n",
    "\n",
    "            treeArr.add(valus.get(s), 1)\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class SegNode:\r\n",
    "#     def __init__(self,left,right) -> None:\r\n",
    "#         self.left=left\r\n",
    "#         self.right=right\r\n",
    "#         self.left_node=None\r\n",
    "#         self.right_node=None\r\n",
    "#         self.sum=0\r\n",
    "    \r\n",
    "#     @classmethod\r\n",
    "#     def build(cls,left,right):\r\n",
    "#         node=SegNode(left,right)\r\n",
    "#         if left==right:\r\n",
    "#             return node\r\n",
    "#         mid=(left+right)//2\r\n",
    "#         l_node=SegNode.build(left,mid)\r\n",
    "#         r_node=SegNode.build(mid+1,right)\r\n",
    "#         node.left_node=l_node\r\n",
    "#         node.right_node=r_node\r\n",
    "#         return node\r\n",
    "    \r\n",
    "#     def count(self,left,right):\r\n",
    "#         if self.right< left or self.left>right:\r\n",
    "#             return 0\r\n",
    "#         if self.left>=left and self.right<=right:\r\n",
    "#             return self.sum\r\n",
    "#         return self.left_node.count(left,right)+self.right_node.count(left,right)\r\n",
    "\r\n",
    "#     def insert(self,index):\r\n",
    "#         self.sum+=1\r\n",
    "#         if self.left==self.right:\r\n",
    "#             return\r\n",
    "#         mid=(self.left+self.right)//2\r\n",
    "#         if index<=mid:\r\n",
    "#             self.left_node.insert(index)\r\n",
    "#         else:\r\n",
    "#             self.right_node.insert(index)\r\n",
    "\r\n",
    "\r\n",
    "class Tree:\r\n",
    "    def __init__(self,count) -> None:\r\n",
    "        self.tree=[0]*(count+1)\r\n",
    "        self.len=count+1\r\n",
    "    \r\n",
    "    def _lowbit(self,index):\r\n",
    "        return index&-index\r\n",
    "\r\n",
    "    def add(self,index):\r\n",
    "        while index<self.len:\r\n",
    "            self.tree[index]+=1\r\n",
    "            index+=self._lowbit(index)\r\n",
    "    \r\n",
    "    def query(self,index):\r\n",
    "        ret=0\r\n",
    "        while index>0:\r\n",
    "            ret+=self.tree[index]\r\n",
    "            index-=self._lowbit(index)\r\n",
    "        return ret\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:\r\n",
    "        # ret=0\r\n",
    "        N=len(nums)\r\n",
    "        presum=[0]*(N+1)\r\n",
    "        # l_bound,r_bound=float('inf'),float('-inf')\r\n",
    "        for i in range(N):\r\n",
    "            sum=nums[i]+presum[i]\r\n",
    "            presum[i+1]=sum\r\n",
    "            # l=sum-upper\r\n",
    "            # r=sum-lower\r\n",
    "            # l_bound=min(l_bound,sum,l,r)\r\n",
    "            # r_bound=max(r_bound,sum,l,r)\r\n",
    "        \r\n",
    "        all_nums=set()\r\n",
    "        for sum in presum:\r\n",
    "            all_nums.add(sum)\r\n",
    "            all_nums.add(sum-lower)\r\n",
    "            all_nums.add(sum-upper)\r\n",
    "\r\n",
    "        all_nums=sorted(all_nums)\r\n",
    "        num_idx={}\r\n",
    "        idx=0\r\n",
    "        for n in all_nums:\r\n",
    "            num_idx[n]=idx\r\n",
    "            idx+=1\r\n",
    "        \r\n",
    "        Len=len(num_idx.values())\r\n",
    "        # node=SegNode.build(l_bound,r_bound)\r\n",
    "        tree=Tree(Len)\r\n",
    "\r\n",
    "        ret=0\r\n",
    "        for n in presum:\r\n",
    "            ret+=tree.query(num_idx[n-lower]+1)-tree.query(num_idx[n-upper])\r\n",
    "            tree.add(num_idx[n]+1)\r\n",
    "        return ret\r\n",
    "\r\n",
    "\r\n",
    "        \r\n",
    "\r\n",
    "\r\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class BitTree:          #树状数组 动态前缀和\n",
    "    def __init__(self, n):\n",
    "        self.tree = [0 for x in range(n + 1)]\n",
    "        self.n = n\n",
    "    #---- 最右侧1的权重\n",
    "    def lowbit(self, i: int) -> int:\n",
    "        return i & (-i)\n",
    "    #----某个位置，加上k\n",
    "    def update(self, i: int, k: int) -> None:\n",
    "        while i <= self.n:\n",
    "            self.tree[i] += k\n",
    "            i += self.lowbit(i)\n",
    "    #----前缀和（实指）   \n",
    "    def presum(self, i: int) -> int:\n",
    "        res = 0\n",
    "        while i > 0:\n",
    "            res += self.tree[i]\n",
    "            i -= self.lowbit(i)\n",
    "        return res\n",
    "\n",
    "class Solution:\n",
    "    def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        n = len(nums)\n",
    "        #---- 前缀和 实指\n",
    "        presum = [0 for _ in range(n + 1)]\n",
    "        for i in range(n):   #虚指\n",
    "            presum[i+1] = presum[i] + nums[i]\n",
    "            #------------------ 以presum 为对象  离散化 + 树状数组----------------------#\n",
    "        #------ 所有的点\n",
    "        all_num = []\n",
    "        for x in presum:\n",
    "            all_num += [x, x - lower, x - upper]\n",
    "        \n",
    "        #------ 离散化\n",
    "        #all_num = list(set(all_num))    #离散化，要去重 都行\n",
    "        all_num.sort()                  #排序\n",
    "\n",
    "        val_id = dict()\n",
    "        for i, x in enumerate(all_num):\n",
    "            val_id[x] = i\n",
    "        #------ 树状数组\n",
    "        BIT = BitTree(len(all_num))\n",
    "        res = 0\n",
    "        for i, x in enumerate(presum): #遍历，往前探\n",
    "            idL = val_id[x - upper]\n",
    "            idR = val_id[x - lower]\n",
    "            res +=  ( BIT.presum(idR + 1) - BIT.presum(idL + 1 - 1) )\n",
    "\n",
    "            ID = val_id[x]\n",
    "            BIT.update(ID + 1, 1)\n",
    "    \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        ln = len(nums)\n",
    "        preSum = [0]\n",
    "        s = 0\n",
    "        for n in nums:\n",
    "            s += n \n",
    "            preSum.append(s)\n",
    "        '''\n",
    "        对于每个下标i，我们需要求lower<=preSum[i] - preSum[j]<=upper出现的个数(j=[0:i - 1])\n",
    "        因为lower、upper和perSum[i]为常数，可以变换一下条件：preSum[i] - upper<=perSum[j] <= preSum[i] - lower\n",
    "        相当于：对于每个下标i，我们需要求perSum[j]的值在preSum[i] - upper和preSum[i] - lower之间的个数(j=[0:i - 1])\n",
    "        可以维护一个树状数组tlist，tlist[v]表示perSum[j]的值在[0:v]区间内的个数和，则所求即\n",
    "        tlist[preSum[i] - lower] - tlist[preSum[i] - upper - 1]\n",
    "        '''\n",
    "        # 去重并离散化\n",
    "        dic = defaultdict(int)\n",
    "        sums = set()\n",
    "        for s in preSum:\n",
    "            sums.add(s)\n",
    "            sums.add(s - upper)\n",
    "            sums.add(s - lower)\n",
    "        sums = list(sums)\n",
    "        sums.sort()\n",
    "        idx = 0\n",
    "        for s in sums:\n",
    "            dic[s] = idx\n",
    "            idx += 1\n",
    "        bit = [0] * (idx + 1)\n",
    "        ans = 0\n",
    "        for i in range(ln + 1):\n",
    "            l, r, ii = dic[preSum[i] - upper], dic[preSum[i] - lower] + 1, dic[preSum[i]] + 1\n",
    "            ls = 0\n",
    "            while l > 0:\n",
    "                ls += bit[l]\n",
    "                l -= l & (-l)\n",
    "            rs = 0\n",
    "            while r > 0:\n",
    "                rs += bit[r]\n",
    "                r -= r & (-r)\n",
    "            ans += rs - ls\n",
    "            while ii <= idx:\n",
    "                bit[ii] += 1\n",
    "                ii += ii & (-ii)\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    class TreeArray:\n",
    "\n",
    "        def __init__(self, n):\n",
    "            self.n = 0\n",
    "            self.c = [0] * (3 * 100010)\n",
    "\n",
    "        def lowbit(self, x):\n",
    "            return x & -x\n",
    "\n",
    "        \n",
    "        def add(self, idx, x):\n",
    "            while idx <= self.n:\n",
    "                self.c[idx] += x\n",
    "                idx += self.lowbit(idx)\n",
    "        \n",
    "        def getsum(self, idx):\n",
    "            res = 0\n",
    "            while idx > 0:\n",
    "                res += self.c[idx]\n",
    "                idx -= self.lowbit(idx)\n",
    "            \n",
    "            return res\n",
    "\n",
    "    def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        treeArr = Solution.TreeArray(len(nums))\n",
    "\n",
    "        allnum = set()\n",
    "        allnum.add(0)\n",
    "        s = 0\n",
    "        for x in nums:\n",
    "            s += x\n",
    "            allnum.add(s)\n",
    "            allnum.add(s - lower)\n",
    "            allnum.add(s - upper)\n",
    "        \n",
    "        allnum = list(allnum)\n",
    "        allnum.sort()\n",
    "\n",
    "        valus = {}\n",
    "\n",
    "        for x in allnum:\n",
    "            treeArr.n += 1\n",
    "            valus[x] = treeArr.n\n",
    "\n",
    "        res = 0\n",
    "        s = 0\n",
    "        treeArr.add(valus[s], 1)\n",
    "\n",
    "        for n in nums:\n",
    "            s += n\n",
    "            a = valus.get(s - lower)\n",
    "            b = valus.get(s - upper) - 1\n",
    "\n",
    "            res += treeArr.getsum(a) - treeArr.getsum(b)\n",
    "\n",
    "            treeArr.add(valus.get(s), 1)\n",
    "        \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.tr = []\n",
    "        self.m = 0\n",
    "\n",
    "    def lowbit(self, x):\n",
    "        return x & -x\n",
    "\n",
    "    def add(self, x, v):\n",
    "        while x <= self.m:\n",
    "            self.tr[x] += v\n",
    "            x += self.lowbit(x)\n",
    "\n",
    "    def query(self, x):\n",
    "        ans = 0\n",
    "        while x > 0:\n",
    "            ans += self.tr[x]\n",
    "            x -= self.lowbit(x)\n",
    "        return ans\n",
    "\n",
    "    def countRangeSum(self, nums, lower, upper):\n",
    "        s = 0\n",
    "        all_sums = [0]\n",
    "        for num in nums:\n",
    "            s += num\n",
    "            all_sums.extend([s, s - lower, s - upper])\n",
    "        \n",
    "        sorted_unique_sums = sorted(set(all_sums))\n",
    "        ranks = {val: i + 1 for i, val in enumerate(sorted_unique_sums)}\n",
    "        self.m = len(sorted_unique_sums)\n",
    "        self.tr = [0] * (self.m + 1)\n",
    "\n",
    "        ans = 0\n",
    "        self.add(ranks[0], 1)\n",
    "        s = 0\n",
    "        for num in nums:\n",
    "            s += num\n",
    "            left_rank = ranks[s - lower]\n",
    "            right_rank = ranks[s - upper] - 1\n",
    "            ans += self.query(left_rank) - self.query(right_rank)\n",
    "            self.add(ranks[s], 1)\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        def lowbit(x):\n",
    "            return x & - x\n",
    "        \n",
    "        def add(x):\n",
    "            while x <= n:\n",
    "                tree[x] += 1\n",
    "                x += lowbit(x)\n",
    "        \n",
    "        def query(x):\n",
    "            ans = 0\n",
    "            while x > 0:\n",
    "                ans += tree[x]\n",
    "                x -= lowbit(x)\n",
    "            return ans\n",
    "\n",
    "        pre = [0] + list(itertools.accumulate(nums))\n",
    "        ranges = []\n",
    "        for i in range(1, len(pre)):\n",
    "            ranges.append(pre[i - 1])\n",
    "            ranges.append(pre[i] - upper)\n",
    "            ranges.append(pre[i] - lower)\n",
    "        ranges = sorted(list(set(ranges)))\n",
    "        n, res = len(ranges), 0\n",
    "        dic = {}\n",
    "        for i in range(n):\n",
    "            if ranges[i] not in dic:\n",
    "                dic[ranges[i]] = i + 1\n",
    "        tree = [0] * (n + 1)\n",
    "        for i in range(1, len(pre)):\n",
    "            p, q = pre[i], pre[i - 1]\n",
    "            add(dic[q])\n",
    "            res += (query(dic[p - lower]) - \n",
    "                    query(dic[p - upper] - 1))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        # 合并有序数组 nums[lo..mid] 和 nums[mid+1..hi]\n",
    "        def merge(nums, lo, mid, hi):\n",
    "            # 用于辅助合并有序数组\n",
    "            temp = []\n",
    "\n",
    "            # 维护区间 [start, end) 中的元素与 nums[i] 的差在 [lower, upper] 中\n",
    "            start, end = mid + 1, mid + 1\n",
    "            for i in range(lo, mid + 1):\n",
    "                # 如果 nums[i] 对应的区间是 [start, end)，\n",
    "                # 那么 nums[i+1] 对应的区间⼀定会整体右移，类似滑动窗口\n",
    "                while start <= hi and nums[start] - nums[i] < lower:\n",
    "                    start += 1\n",
    "                while end <= hi and nums[end] - nums[i] <= upper:\n",
    "                    end += 1\n",
    "                count.append(end - start)\n",
    "\n",
    "            # 数组双指针技巧，合并两个有序数组\n",
    "            i, j = lo, mid + 1\n",
    "            while i <= mid or j <= hi:\n",
    "                if i > mid or (j <= hi and nums[j] < nums[i]):\n",
    "                    temp.append(nums[j])\n",
    "                    j += 1\n",
    "                else:\n",
    "                    temp.append(nums[i])\n",
    "                    i += 1\n",
    "            nums[lo:hi + 1] = temp\n",
    "\n",
    "        # 将子数组 nums[lo..hi] 排序\n",
    "        def sort(nums, lo, hi):\n",
    "            if lo == hi:\n",
    "                # 单个元素不用排序\n",
    "                return\n",
    "            mid = (lo + hi) // 2\n",
    "            # 先对左半部分数组 nums[lo..mid] 排序\n",
    "            sort(nums, lo, mid)\n",
    "            # 再对右半部分数组 nums[mid+1..hi] 排序\n",
    "            sort(nums, mid + 1, hi)\n",
    "            # 将两部分有序数组合并成⼀个有序数组\n",
    "            merge(nums, lo, mid, hi)\n",
    "\n",
    "        # 存储结果\n",
    "        count = []\n",
    "        # 构建前缀和数组\n",
    "        presums = [0]\n",
    "        for num in nums:\n",
    "            presums.append(presums[-1] + num)\n",
    "        # 对前缀和数组进行归并排序\n",
    "        sort(presums, 0, len(presums) - 1)\n",
    "        return sum(count)\n",
    "# 归并排序"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class BIT:\n",
    "    def __init__(self, n):\n",
    "        self.arr = [0]*n\n",
    "    def lowbit(self, x):\n",
    "        return x & -x\n",
    "    def add(self, i, x):\n",
    "        while i < len(self.arr):\n",
    "            self.arr[i] += x\n",
    "            i += self.lowbit(i)\n",
    "    def query(self, i):\n",
    "        res = 0\n",
    "        while i > 0:\n",
    "            res += self.arr[i]\n",
    "            i -= self.lowbit(i)\n",
    "        return res\n",
    "class Solution:\n",
    "    def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        v = set()\n",
    "        sm = 0\n",
    "        for x in nums:\n",
    "            sm += x\n",
    "            v.add(sm)\n",
    "            v.add(sm-lower)\n",
    "            v.add(sm-upper)\n",
    "        i = 1\n",
    "        maps = {}\n",
    "        for x in sorted(v):\n",
    "            maps[x] = i\n",
    "            i+=1\n",
    "        bit = BIT(len(maps)+5)\n",
    "        res = 0\n",
    "        sm = 0\n",
    "        for x in nums:\n",
    "            sm += x\n",
    "            if lower<=sm<=upper:\n",
    "                res +=1\n",
    "            res += bit.query(maps[sm-lower]) - bit.query(maps[sm-upper]-1)\n",
    "            bit.add(maps[sm], 1)\n",
    "        return res\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        def lowbit(x):\n",
    "            return x & -x\n",
    "        \n",
    "        def query(x):\n",
    "            ans = 0\n",
    "            while x > 0:\n",
    "                ans += self.tree[x]\n",
    "                x -= lowbit(x)\n",
    "            return ans\n",
    "        \n",
    "        def add(x, incr):\n",
    "            while x < len(self.tree):\n",
    "                self.tree[x] += incr\n",
    "                x += lowbit(x)\n",
    "        \n",
    "        n = len(nums)\n",
    "        pre = [0] * (n + 1)\n",
    "        for i, v in enumerate(nums, 1):\n",
    "            pre[i] = pre[i - 1] + nums[i - 1]\n",
    "        s = set()\n",
    "        for v in pre:\n",
    "            s.add(v)\n",
    "            s.add(v - upper)\n",
    "            s.add(v - lower)\n",
    "        mp = dict()\n",
    "        idx = 1\n",
    "        for v in sorted(s):\n",
    "            mp[v] = idx\n",
    "            idx += 1\n",
    "        self.tree = [0] * (len(mp) + 1)\n",
    "        ans = 0\n",
    "        for v in pre:\n",
    "            l, r = mp[v - upper] - 1, mp[v - lower]\n",
    "            ans += query(r) - query(l)\n",
    "            add(mp[v], 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Segtree:\n",
    "\n",
    "    def __init__(self, n):\n",
    "        self.n=n\n",
    "        size=2<<(len(bin(n))-2)\n",
    "        self.sum=[0]*size\n",
    "\n",
    "    def add(self,o,l,r,idx,val):\n",
    "        if l==r:\n",
    "            self.sum[o]+=val\n",
    "            return\n",
    "        mid=(l+r)//2\n",
    "        if idx<=mid:\n",
    "            self.add(o*2,l,mid,idx,val)\n",
    "        else:\n",
    "            self.add(o*2+1,mid+1,r,idx,val)\n",
    "        self.sum[o]=self.sum[o*2]+self.sum[o*2+1]\n",
    "\n",
    "    def query(self,o,l,r,L,R):\n",
    "        if l>=L and r<=R:\n",
    "            return self.sum[o]\n",
    "        mid=(l+r)//2\n",
    "        s=0\n",
    "        if L<=mid:\n",
    "            s+=self.query(o*2,l,mid,L,R)\n",
    "        if R>=mid+1:\n",
    "            s+=self.query(o*2+1,mid+1,r,L,R)\n",
    "        return s\n",
    "\n",
    "class Solution:\n",
    "    def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        presum=list(accumulate(nums,initial=0))\n",
    "        tmp=[]\n",
    "        for p in presum:\n",
    "            tmp.extend([p,p-lower,p-upper])\n",
    "        tmp=list(set(tmp))\n",
    "        tmp.sort()\n",
    "        val_id={}\n",
    "        for i,num in enumerate(tmp):\n",
    "            val_id[num]=i+1\n",
    "\n",
    "        st=Segtree(len(tmp))\n",
    "        n=len(tmp)\n",
    "        res=0   \n",
    "        for i,p in enumerate(presum):\n",
    "            if i==0:\n",
    "                st.add(1,1,n,val_id[0],1)\n",
    "                continue\n",
    "            L=val_id[p-upper]\n",
    "            R=val_id[p-lower]\n",
    "            res+=st.query(1,1,n,L,R)\n",
    "            st.add(1,1,n,val_id[p],1)\n",
    "\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 树状数组\n",
    "class BIT:\n",
    "    def __init__(self, n):\n",
    "        self.n = n\n",
    "        self.c = [0 for _ in range(n + 1)] # 树状数组从下标1开始存储，表示原数组a下标区间(i-lowbit(i), i]的和（原数组a也从下标1开始存储）\n",
    "\n",
    "    def _lowbit(self, x): # lowbit指x二进制下最低位的1和后面所有的0组成的数\n",
    "        return x & (-x)\n",
    "\n",
    "    # 将原数组a[i]的值增加x，修改树状数组对应的位置\n",
    "    def update(self, i, x):\n",
    "        while i <= self.n:\n",
    "            self.c[i] += x\n",
    "            i += self._lowbit(i)\n",
    "\n",
    "    # 求原数组a下标区间[1,i]的和（前i项的和）\n",
    "    def query(self, i):\n",
    "        ans = 0\n",
    "        while i > 0:\n",
    "            ans += self.c[i]\n",
    "            i -= self._lowbit(i)\n",
    "        return ans\n",
    "    \n",
    "    # 求原数组a下标区间[i,j]的和\n",
    "    def query1(self, i, j):\n",
    "        return self.query(j) - self.query(i - 1)\n",
    "    \n",
    "class Solution:\n",
    "    def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        s = set()\n",
    "        for x in accumulate(nums, initial=0):\n",
    "            s.add(x)\n",
    "            s.add(x - upper)\n",
    "            s.add(x - lower)\n",
    "        sorted_l = sorted(s)\n",
    "        d = {x: i + 1 for i, x in enumerate(sorted_l)}\n",
    "        pre_sum = 0\n",
    "        tree = BIT(len(sorted_l))\n",
    "        tree.update(d[pre_sum] ,1)\n",
    "        ans = 0\n",
    "        for num in nums:\n",
    "            pre_sum += num\n",
    "            ans += tree.query1(d[pre_sum - upper], d[pre_sum - lower])\n",
    "            tree.update(d[pre_sum], 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "#         #仿照官方归并排序的思路去写的\n",
    "#         s = [0]*(len(nums)+1)\n",
    "#         for i in range(len(nums)):\n",
    "#             s[i+1] = s[i] + nums[i]\n",
    "#         res = 0\n",
    "#         def countRangeSumRecursive(s,lower,uper,left,right):\n",
    "#             '''\n",
    "#             s:前缀和数组\n",
    "#             lower:下限\n",
    "#             upper:上限\n",
    "#             [left,right]要归并的左右边界，均为闭区间\n",
    "#             返回符合的前缀和数目\n",
    "#             递归后进行逐层的返回\n",
    "#             '''\n",
    "#             if left==right:\n",
    "#                 return 0\n",
    "#             else:\n",
    "#                 mid = (left+right)//2\n",
    "#                 #[left,mid] [mid+1,right]\n",
    "#                 n1 = countRangeSumRecursive(s,lower,upper,left,mid)\n",
    "#                 n2 = countRangeSumRecursive(s,lower,upper,mid+1,right)\n",
    "#                 res = n1+n2\n",
    "            \n",
    "#             #统计下标对的数量\n",
    "#             i = left\n",
    "#             l = mid + 1\n",
    "#             r = mid + 1\n",
    "#             #在[l,r)这个区间内的都是有效的下标对\n",
    "#             #l的含义:第一个大于等于lower的数\n",
    "#             #r的含义:第一个大于upper的数\n",
    "#             while i<=mid:\n",
    "#                 while  l<=right and s[l]-s[i]<lower:\n",
    "#                     l += 1\n",
    "#                 while r<=right and s[r] -s[i]<=upper:\n",
    "#                     r += 1\n",
    "#                 res += (r - l)\n",
    "#                 i += 1\n",
    "            \n",
    "#             #合并设置辅助数组\n",
    "#             tmp = [0] * (right-left+1)\n",
    "#             p1 = left\n",
    "#             p2 = mid + 1\n",
    "#             p0 = 0\n",
    "#             while p1<=mid or p2<=right:\n",
    "#                 if p1>mid:\n",
    "#                     tmp[p0] = s[p2]\n",
    "#                     p0 += 1\n",
    "#                     p2 += 1\n",
    "#                 elif p2>right:\n",
    "#                     tmp[p0] = s[p1]\n",
    "#                     p0 += 1\n",
    "#                     p1 += 1\n",
    "#                 else:\n",
    "#                     if s[p1]>s[p2]:\n",
    "#                         tmp[p0] = s[p2]\n",
    "#                         p0 += 1\n",
    "#                         p2 += 1\n",
    "#                     else:\n",
    "#                         tmp[p0] = s[p1]\n",
    "#                         p0 += 1\n",
    "#                         p1 += 1\n",
    "#             for i in range(len(tmp)):\n",
    "#                 s[left+i] = tmp[i]\n",
    "#             return res\n",
    "        \n",
    "#         # 如nums中[0,0]区间,[0,2]区间都对应了从0开始,如果这里不是从0开始的话，就会漏掉第一个数单独形成的区间\n",
    "#         return countRangeSumRecursive(s,lower,upper,0,len(s)-1)\n",
    "\n",
    "#单点修改，区间查询，可以使用树状数组\n",
    "class Solution:\n",
    "    def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:            \n",
    "        set_ = set()\n",
    "        s = 0\n",
    "        set_.add(0)\n",
    "        for i in range(len(nums)):\n",
    "            s += nums[i]\n",
    "            set_.add(s)\n",
    "            set_.add(s-lower)\n",
    "            set_.add(s-upper)\n",
    "        s=sorted(set_) \n",
    "        mp={v:i for i,v in enumerate(s,start=1)} #每个数对应的下标\n",
    "        a=[mp[i] for i in set_] #将数转换成下标的形式\n",
    "        maxv=300010\n",
    "        self.tree=[0]*maxv\n",
    "        self.add(mp[0],1) #先把前缀和为0的放进去\n",
    "        ans = 0\n",
    "        s1 = 0\n",
    "        for num in nums:\n",
    "            s1 += num\n",
    "            ans += (self.query(mp[s1-lower]) - self.query(mp[s1-upper]-1))\n",
    "            self.add(mp[s1],1)\n",
    "        return ans    \n",
    "\n",
    "    def lowbit(self,x):\n",
    "        return x&(-x)\n",
    "    def add(self,i, delta):      # 单点更新：执行+delta\n",
    "        while i<len(self.tree):\n",
    "            self.tree[i] += delta\n",
    "            i += self.lowbit(i)\n",
    "\n",
    "    def query(self,i):           # 前缀和查询\n",
    "        presum = 0\n",
    "        while i>0:\n",
    "            presum += self.tree[i]\n",
    "            i -= self.lowbit(i)\n",
    "        return presum\n",
    "\n",
    "\n",
    "\n",
    "# class Solution {\n",
    "#     public int countRangeSum(int[] nums, int lower, int upper) {\n",
    "#         long s = 0;\n",
    "#         long[] sum = new long[nums.length + 1];\n",
    "#         for (int i = 0; i < nums.length; ++i) {\n",
    "#             s += nums[i];\n",
    "#             sum[i + 1] = s;\n",
    "#         }\n",
    "#         return countRangeSumRecursive(sum, lower, upper, 0, sum.length - 1);\n",
    "#     }\n",
    "\n",
    "#     public int countRangeSumRecursive(long[] sum, int lower, int upper, int left, int right) {\n",
    "#         if (left == right) {\n",
    "#             return 0;\n",
    "#         } else {\n",
    "#             int mid = (left + right) / 2;\n",
    "#             int n1 = countRangeSumRecursive(sum, lower, upper, left, mid);\n",
    "#             int n2 = countRangeSumRecursive(sum, lower, upper, mid + 1, right);\n",
    "#             int ret = n1 + n2;\n",
    "\n",
    "#             // 首先统计下标对的数量\n",
    "            \n",
    "#             int i = left;\n",
    "#             int l = mid + 1;\n",
    "#             int r = mid + 1;\n",
    "#             while (i <= mid) {\n",
    "#                 while (l <= right && sum[l] - sum[i] < lower) {\n",
    "#                     l++;\n",
    "#                 }\n",
    "#                 while (r <= right && sum[r] - sum[i] <= upper) {\n",
    "#                     r++;\n",
    "#                 }\n",
    "#                 ret += r - l;\n",
    "#                 i++;\n",
    "#             }\n",
    "\n",
    "#             // 随后合并两个排序数组\n",
    "#             int[] sorted = new int[right - left + 1];\n",
    "#             int p1 = left, p2 = mid + 1;\n",
    "#             int p = 0;\n",
    "#             while (p1 <= mid || p2 <= right) {\n",
    "#                 if (p1 > mid) {\n",
    "#                     sorted[p++] = (int) sum[p2++];\n",
    "#                 } else if (p2 > right) {\n",
    "#                     sorted[p++] = (int) sum[p1++];\n",
    "#                 } else {\n",
    "#                     if (sum[p1] < sum[p2]) {\n",
    "#                         sorted[p++] = (int) sum[p1++];\n",
    "#                     } else {\n",
    "#                         sorted[p++] = (int) sum[p2++];\n",
    "#                     }\n",
    "#                 }\n",
    "#             }\n",
    "#             for (int j = 0; j < sorted.length; j++) {\n",
    "#                 sum[left + j] = sorted[j];\n",
    "#             }\n",
    "#             return ret;\n",
    "#         }\n",
    "#     }\n",
    "# }"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        n = len(nums)\n",
    "        preFix = [0]+list(accumulate(nums))\n",
    "        rank = {}\n",
    "        newArr = set(preFix)\n",
    "        for each in preFix:\n",
    "            newArr.add(each-lower)\n",
    "            newArr.add(each-upper)\n",
    "        newArr = sorted(set(newArr))\n",
    "        for i,j in enumerate(newArr,1):\n",
    "            rank[j] = i\n",
    "        MX = len(rank) + 1\n",
    "        bit = [0]*MX\n",
    "        def lowbit(i):\n",
    "            return i&-i\n",
    "\n",
    "        def update(i,val=1):\n",
    "            while i < MX:\n",
    "                bit[i] += val\n",
    "                i += lowbit(i)\n",
    "\n",
    "        def query(i):\n",
    "            res = 0\n",
    "            while i > 0:\n",
    "                res += bit[i]\n",
    "                i -= lowbit(i)\n",
    "            return res\n",
    "        ans = 0\n",
    "        for each in preFix:\n",
    "            left,right = each-upper,each-lower\n",
    "            ans += query(rank[right]) - query(rank[left]-1)\n",
    "            update(rank[each],1)\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class SegmentTreeLazy:\n",
    "    def __init__(self, n):\n",
    "        self.n = 1 << (n-1).bit_length()\n",
    "        self.X = [0] * (self.n * 2)\n",
    "        self.lazy = [0] * (self.n * 2)  # i -> (2i, 2i+1)\n",
    "    \n",
    "    def query(self, l, r):  # [l, r]\n",
    "        l += self.n\n",
    "        r += self.n\n",
    "        return self._query(l, r, 1, self.n, 2*self.n - 1)\n",
    "    \n",
    "    def _query(self, l, r, i, il, ir):  # query [l, r], at index i governing [il, ir]\n",
    "        if i < self.n and self.lazy[i] != 0:\n",
    "            self.pushdown(i, ir - il + 1)\n",
    "        if l == il and r == ir:\n",
    "            return self.X[i]\n",
    "        im = (il + ir) // 2\n",
    "        if r <= im:\n",
    "            return self._query(l, r, i*2, il, im)\n",
    "        elif l > im:\n",
    "            return self._query(l, r, i*2+1, im+1, ir)\n",
    "        return self._query(l, im, i*2, il, im) + self._query(im+1, r, i*2+1, im+1, ir)\n",
    "    \n",
    "    def add_on(self, l, r, v):  # [l, r]\n",
    "        l += self.n\n",
    "        r += self.n\n",
    "        self._add_on(l, r, v, 1, self.n, 2*self.n - 1)\n",
    "    \n",
    "    def _add_on(self, l, r, v, i, il, ir):  # add on [l, r], at index i governing [il, ir]\n",
    "        if i < self.n and self.lazy[i] != 0:\n",
    "            self.pushdown(i, ir - il + 1)\n",
    "        if l == il and r == ir:\n",
    "            self.X[i] += v * (r - l + 1)\n",
    "            self.lazy[i] += v\n",
    "            return\n",
    "        im = (il + ir) // 2\n",
    "        if r <= im:\n",
    "            self._add_on(l, r, v, i*2, il, im)\n",
    "        elif l > im:\n",
    "            self._add_on(l, r, v, i*2+1, im+1, ir)\n",
    "        else:\n",
    "            self._add_on(l, im, v, i*2, il, im)\n",
    "            self._add_on(im+1, r, v, i*2+1, im+1, ir)\n",
    "        self.X[i] = self.X[i*2] + self.X[i*2+1]\n",
    "    \n",
    "    def pushdown(self, i, length):\n",
    "        for j in 2*i, 2*i+1:\n",
    "            self.X[j] += self.lazy[i] * (length // 2)\n",
    "            self.lazy[j] += self.lazy[i]\n",
    "        self.lazy[i] = 0\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        n = len(nums)\n",
    "        a = list(accumulate(nums, initial=0))\n",
    "        x = a + [v-lower for v in a] + [v-upper for v in a]\n",
    "        x = sorted(set(x))\n",
    "        d = {v:i for i,v in enumerate(x)}\n",
    "        tree = SegmentTreeLazy(len(d))\n",
    "        ans = 0\n",
    "        for j in range(n):\n",
    "            i = d[a[j]]\n",
    "            tree.add_on(i, i, 1)\n",
    "            lo, hi = a[j+1] - upper, a[j+1] - lower\n",
    "            ans += tree.query(d[lo], d[hi])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class SegmentTree:\n",
    "    def __init__(self, data, merge): \n",
    "        self.data = data\n",
    "        self.n = len(data)\n",
    "        self.tree = [None] * (4 * self.n)\n",
    "        self._merge = merge # lambda function\n",
    "        if self.n:\n",
    "            self._build(0, 0, self.n-1)\n",
    "\n",
    "    def query(self, ql, qr):\n",
    "        return self._query(0, 0, self.n-1, ql, qr)\n",
    "\n",
    "    def update(self, index, value):\n",
    "        self.data[index] = value\n",
    "        self._update(0, 0, self.n-1, index)\n",
    "\n",
    "    def _build(self, tree_index, l, r):\n",
    "        if l == r:\n",
    "            self.tree[tree_index] = self.data[l]\n",
    "            return\n",
    "        mid = (l+r) // 2\n",
    "        left, right = 2 * tree_index + 1, 2 * tree_index + 2 # left, right child\n",
    "        self._build(left, l, mid)\n",
    "        self._build(right, mid+1, r)\n",
    "        self.tree[tree_index] = self._merge(self.tree[left], self.tree[right])\n",
    "\n",
    "    def _query(self, tree_index, l, r, ql, qr):\n",
    "        ## querying [ql,..,qr]; currently at tree_index, representing [l,..,r]\n",
    "        if l == ql and r == qr:\n",
    "            return self.tree[tree_index]\n",
    "        mid = (l+r) // 2\n",
    "        left, right = tree_index * 2 + 1, tree_index * 2 + 2\n",
    "        if qr <= mid:\n",
    "            return self._query(left, l, mid, ql, qr)\n",
    "        elif ql > mid:\n",
    "            return self._query(right, mid+1, r, ql, qr)\n",
    "        return self._merge(self._query(left, l, mid, ql, mid), \n",
    "                          self._query(right, mid+1, r, mid+1, qr))\n",
    "\n",
    "    def _update(self, tree_index, l, r, index):\n",
    "        ## updating index; currently at tree_index, representing [l,..,r]\n",
    "        if l == r == index:\n",
    "            self.tree[tree_index] = self.data[index]\n",
    "            return\n",
    "        mid = (l+r)//2\n",
    "        left, right = 2 * tree_index + 1, 2 * tree_index + 2\n",
    "        if index > mid:\n",
    "            self._update(right, mid+1, r, index)\n",
    "        else:\n",
    "            self._update(left, l, mid, index)\n",
    "        self.tree[tree_index] = self._merge(self.tree[left], self.tree[right])\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        x = list(itertools.accumulate(nums, initial=0))\n",
    "        x = x + [p-lower for p in x] + [p-upper for p in x]\n",
    "        x = sorted(set(x))\n",
    "        x2i = {v:i for i,v in enumerate(x)}\n",
    "        count = [0] * len(x)\n",
    "        t = SegmentTree(count, lambda a,b: a+b)\n",
    "        t.update(x2i[0], 1)\n",
    "        ans = s = 0\n",
    "        for i in nums:\n",
    "            s += i\n",
    "            ans += t.query(x2i[s-upper], x2i[s-lower])\n",
    "            v = t.data[x2i[s]]\n",
    "            t.update(x2i[s], v+1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from bisect import bisect_left\n",
    "class Solution:\n",
    "    def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        # 集合离散化：将可能用到的数值加入到集合中，排序后用哈希表离散映射\n",
    "        pre, s = 0, {0}\n",
    "        for x in nums:\n",
    "            pre += x\n",
    "            s.add(pre)\n",
    "            s.add(pre - upper)\n",
    "            s.add(pre - lower)\n",
    "        \n",
    "        tmp = sorted(list(s))\n",
    "        \n",
    "        mp = {}\n",
    "        for i, x in enumerate(tmp):\n",
    "            mp[x] = i\n",
    "        \n",
    "        n, res = len(tmp), 0\n",
    "        tree = [0] * (n + 1)\n",
    "        def lowbit(x):\n",
    "            return x & (-x)\n",
    "        def update(idx, val):\n",
    "            while idx <= n:\n",
    "                tree[idx] += val \n",
    "                idx += lowbit(idx)\n",
    "        def query(idx):\n",
    "            res = 0\n",
    "            while idx > 0:\n",
    "                res += tree[idx]\n",
    "                idx -= lowbit(idx)\n",
    "            return res \n",
    "        \n",
    "        pre = 0\n",
    "        update(mp[0] + 1, 1)\n",
    "\n",
    "\n",
    "        for x in nums:\n",
    "            pre += x\n",
    "            res += query(mp[pre - lower] + 1) - query(mp[pre - upper])\n",
    "            update(mp[pre] + 1, 1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "##线段树\n",
    "class NodeIndexedTree:\n",
    "    def __init__(self, length):\n",
    "        self.tree = [0]*(length+1)\n",
    "        self.n = length\n",
    "    def update(self, x, val):\n",
    "        while x <= self.n:\n",
    "            self.tree[x] += val\n",
    "            x += self.lowbit(x)\n",
    "    def query(self, x):\n",
    "        ans = 0\n",
    "        while x > 0:\n",
    "            ans += self.tree[x]\n",
    "            x -= self.lowbit(x)\n",
    "        return ans\n",
    "\n",
    "    def lowbit(self, x):\n",
    "        return x & (-x)\n",
    "\n",
    "## preSum[j] -upper<x < presum[j] - lower\n",
    "## upper > -x > -presum[j] +lower \n",
    "class Solution:\n",
    "    def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        ##求前缀和\n",
    "        n = len(nums)\n",
    "        presum = [0]*(n+1)\n",
    "        sum_v = 0\n",
    "        for i in range(n):\n",
    "            sum_v += nums[i]\n",
    "            presum[i+1] = sum_v\n",
    "        a = set()\n",
    "        for x in presum:\n",
    "            a.add(x)\n",
    "            a.add(x-lower)\n",
    "            a.add(x-upper)\n",
    "        ##离散化\n",
    "        value2Id = {v: i for i, v in enumerate(sorted(a))}\n",
    "        res = 0\n",
    "        tree = NodeIndexedTree(len(a))\n",
    "        for i in range(len(presum)):\n",
    "            left = value2Id.get(presum[i] - upper) \n",
    "            right=value2Id.get(presum[i] - lower)\n",
    "            count = tree.query(right+1) - tree.query(left)\n",
    "            res += count\n",
    "            tree.update(value2Id[presum[i]]+1, 1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class BinaryIndexedTree:\n",
    "    __slots__ = [\"n\", \"c\"]\n",
    "\n",
    "    def __init__(self, n):\n",
    "        self.n = n\n",
    "        self.c = [0] * (n + 1)\n",
    "\n",
    "    def update(self, x: int, delta: int):\n",
    "        while x <= self.n:\n",
    "            self.c[x] += delta\n",
    "            x += x & -x\n",
    "\n",
    "    def query(self, x: int) -> int:\n",
    "        s = 0\n",
    "        while x > 0:\n",
    "            s += self.c[x]\n",
    "            x -= x & -x\n",
    "        return s\n",
    "class Solution:\n",
    "    def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        ret = 0\n",
    "        tmp = set()\n",
    "        pre = list(accumulate(nums, initial=0))\n",
    "        for x in pre:\n",
    "            tmp.add(x)\n",
    "            tmp.add(x - lower)\n",
    "            tmp.add(x - upper)\n",
    "        rank = {x: i + 1 for i, x in enumerate(sorted(list(tmp)))}\n",
    "        btree = BinaryIndexedTree(len(tmp))\n",
    "        for x in pre:\n",
    "            ret += btree.query(rank[x - lower]) - btree.query(rank[x - upper] - 1)\n",
    "            btree.update(rank[x], 1)\n",
    "        return ret"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
